Rezolvare PBinfo #3575

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 \( {C}_{i} \) – 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ă, începand cu el, î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ța

Se cere numărul de beri pe care le va cumpăra fiecare prieten k în limita sumei x de bani de care dispune. În caz că x 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 \( {C}_{1}, {C}_{2}, …, {C}_{N} \), separate prin câte un spaţiu, reprezentând costurile berilor preferate de fiecare prieten. Berea pentru prietenul i are costul \( {C}_{i} \).
Fiecare din următoarele T linii conţine câte două numere separate printr-un spaţiu:
\( {k}_{1} {x}_{1} \)
\( {k}_{2} {x}_{2} \)
…
\( {k}_{T} {x}_{T} \)
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 \( {D}_{i} \) reprezentând numărul de beri pe care le va cumpăra prietenul \( {k}_{i} \) cu suma de bani \( {x}_{i} \) in condiţiile problemei.

Restricții și precizări

• 1 ≤ N ≤ 15.000
• 1 ≤ T ≤ 10.000
• \( 1 ≤ {C}_{i} ≤ 100 \)
• \( 1 ≤ {k}_{i} ≤ N \)
• \( 1 ≤ {x}_{i} ≤ 3.000.000 \)
• 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ă.

Exemplu:

br.in

5 4
10 5 15 22 13
1 32
4 50
1 9
4 200

br.out

3
4
0
5

Explicație

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.