Pentru că Phineas şi Ferb s-au hotărât să instaureze "viarna":https://www.youtube.com/watch?v=BWETBoOPHS8 în orasul Danville, "veveriţele":https://www.youtube.com/watch?v=iYoKCLY965A s-au decis în sfârşit să o lase în pace pe Candace şi vor să îşi facă provizii de ghinde.

Iniţial veveriţele au un număr $X$ de ghinde. În fiecare din următoarele $N$ zile, copacul din curtea familiei Flynn-Fletcher are un anumit număr de ghinde (În ziua $1$ are $v[1$] ghinde, în ziua $2$ $v[2$], ... în ziua $N$ $v[N$]).
Veveriţele au un mod interesant de a-şi aduna ghinde. Acestea sunt fericite dacă în fiecare zi **numărul lor de ghinde are valoarea cel puţin egală cu numărul de ghinde care se află în ziua respectivă în copac**.

Iniţial veveriţele au un număr $X$ de ghinde. Veveriţele vor colecta ghinde pe parcursul a $N$ zile, in ziua $i$ copacul din curtea familiei Flynn-Fletcher va avea $A{~i~}$ ghinde.
 
Veveriţele au un mod interesant de a-şi aduna ghinde. Acestea sunt fericite dacă în fiecare zi numărul lor de ghinde este *mai mare sau egal* ca numărul de ghinde care se află în ziua respectivă în copac.

La finalul fiecărei zile, acestea pot să-şi adune la colecţie toate ghindele care au fost în copac în ziua aceea. (Mai întâi trebuie să se respecte condiţia, apoi pot să adune ghindele)

Pentru că veveriţele ştiu cât de des Phineas şi Ferb observă dipariţia lui Perry ornitorincul, nu ar vrea să riste ca aceştia să observe şi ghindele lipsă din copac. Prin urmare, vor să minimizeze numărul de zile în care le fură din copac.

Pentru că veveriţele ştiu cât de des Phineas şi Ferb observă dispariţia lui Perry ornitorincul, nu ar vrea să riste ca aceştia să observe şi ghindele lipsă din copac. Prin urmare, vor să minimizeze numărul de zile în care le fură din copac.

Pentru $Q$ scenarii posibile în care se dă numărul iniţial de ghinde pe care îl au veveriţele, se cere **numărul minim de zile** în care veveriţele trebuie să fure ghindele din copac pentru a se respecta condiţiile, sau să spuneţi dacă acest lucru nu este posibil.

Pentru $Q$ scenarii posibile în care se dă numărul iniţial de ghinde pe care îl au veveriţele, se cere numărul **minim** de zile în care veveriţele trebuie să fure ghindele din copac pentru a se respecta condiţiile, sau să spuneţi dacă acest lucru nu este posibil.

h2. Date de intrare

h2. Restricţii
* $1 ≤ $N, Q$ ≤ 10^5^$

* $1 ≤ $v[i$] ≤ 10^9^$
* $v[i$] ≤ $v[i + 1]$ pentru $1 ≤ i ≤ N - 1$

* $1 ≤ $A{~i~}$ ≤ 10^9^$
* $A{~i~}$ ≤ $A{~i+1~}$ pentru $1 ≤ i ≤ N - 1$

h2. Subtaskuri

* **Subtaskul 1 (20 de puncte):** $N,Q ≤ 2000$
* **Subtaskul 2 (20 de puncte):** $v[i] ≤ 100$, pentru $1 ≤ i ≤ N, N,Q ≤ 10^5^$
* **Subtaskul 3 (60 de puncte):** restricţiile iniţiale

* *$Subtaskul 1 (20 de puncte):$* $N,Q ≤ 2000$
* *$Subtaskul 2 (20 de puncte):$* $A{~i~}$ ≤ $100$, pentru $1 ≤ i ≤ N, N,Q ≤ 10^5^$
* *$Subtaskul 3 (60 de puncte):$* restricţiile iniţiale

h2. Exemplu