N prieteni, numerotaţi de la 1 la N, beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte Ci – costul berii lui preferate. Din când în când, câte un prieten, fie el k, cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, inclusiv lui, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.
Cerinţă
Se cere numărul de beri pe care le va cumpăra fiecare prieten în limita sumei de bani de care dispune. În cazul că suma este mai mare decât costul berilor pentru toţi prietenii de la masă, se vor achiziţiona maxim N beri.
Date de intrare
Prima linie a fişierului de intrare br.in conţine două numere naturale N şi T separate printr-un spaţiu reprezentând numărul de prieteni şi respectiv numărul de prieteni care doresc să facă cinste prietenilor săi.
A doua linie a fişierului de intrare conţine N numere naturale C1, C2 ... CN, separate prin câte un spaţiu, reprezentând costurile berilor preferate de fiecare prieten. Berea pentru prietenul i are costul Ci.
Fiecare dintre următoarele T linii conţine câte două numere separate printr-un spaţiu ki xi (1<=i<=N) precizând indicele câte unui prieten care face cinste şi respectiv suma de bani de care acesta dispune.
Date de ieşire
Fişierul de ieşire br.out va conţine T linii, fiecare cu un singur număr Di reprezentând numărul de beri pe care le va cumpăra prietenul ki cu suma de bani xi in condiţiile problemei.
Restricţii
1 ≤ N ≤ 15000
1 ≤ T ≤ 10000
1 ≤ Ci ≤ 100
1 ≤ ki ≤ N
1 ≤ xi ≤ 3000000
Un program corect, care se încadrează în timp pentru T≤4000, va obţine cel puţin 30 de puncte
Un program corect, care se încadrează în timp pentru N≤2000, va obţine cel puţin 60 de puncte
Prietenii beau numai berea lor preferată.
Exemple
br.in
br.out
Explicaţii
5 4
10 5 15 22 13
1 32
4 50
1 9
4 200
3
4
0
5
Prietenul 1 cumpără câte o bere pentru el şi pentru prietenii 2, 3. Costul celor 3 beri este 30.
Prietenul 4 cumpără 4 beri: câte una pentru el şi pentru prietenii 5, 1, 2. Costul celor 4 beri este 50.
Cu 9 bani prietenul 1 nu poate cumpăra nici măcar berea lui.
Prietenul 4 cumpără 5 beri. Costul celor 5 beri este sub limita de cost 200.