br

$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ă, 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 $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, \ldots 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$
• $\dots$
• $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 \leq N \leq 15 \ 000$
• $1 \leq T \leq 10 \ 000$
• $1 \leq C_i \leq 100$
• $1 \leq k_i \leq N$
• $1 \leq x_i \leq 3 \ 000 \ 000$
• Un program corect, care se încadrează în timp pentru $T \leq 4 \ 000$, va obţine cel puţin $30$ de puncte
• Un program corect, care se încadrează în timp pentru $N \leq 2 \ 000$, 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$.