Kiloforces

— Fă, eu fac cartă du-te drecu. Tu mă înjuri pe mine mă? Tu știai că vine lupu?
— Bă Bahoi, ai dreptate să moară familia mea, te rog să mă ierți. Uite acuma, mă voi plesni, mă voi băga în penitență, Bahoi, ca să-mi cer scuze, că tu ești artistul artistilor, da?

Vadim este un tânăr foarte talentat și pasionat de informatică. Plin de spiritul Crăciunului, acesta decide să își petreacă vacanța de iarnă participând la cât mai multe concursuri, pe platforma lui preferată, $\text{Kiloforces}$. Acolo, sistemul de punctare este puțin diferit. Dacă concursul are $K$ probleme, a $i$-a valorând $p_i$ puncte, atunci în momentul în care el rezolvă problema $j$, se adună la scorul total $p_j$ puncte, iar din punctajele problemelor nerezolvate se scad $t_j$ puncte. Regulile platformei permit ca la oricare moment de timp să existe probleme cu punctaj negativ (pe care Vadim va trebui să le rezolve).

Cerință

Vadim primește $N$ probleme, pentru fiecare știind valorile $p_i$ și $t_i$. Acesta, în următoarele $Q$ zile, își alege un interval $[l, r]$ și se întreabă care este scorul maxim pe care-l poate obține, dacă participă la un concurs alcătuit din problemele $l, l+1, l+2, \dots, r-1, r$. Ajutați-l pe Vadim să își răspundă la cele $Q$ întrebări, altfel veți ajunge pe lista de copii obraznici a Moșului.

Date de intrare

Pe prima linie se află $N$ și $Q$. Pe următoarele 2 linii se vor afla câte $N$ valori ($p_i$, respectiv $t_i$), iar pe ultimele $Q$ linii se află întrebările puse de Vadim.

Date de ieșire

Pe fiecare din următoarele $Q$ linii se vor afla răspunsurile la întrebarile lui Vadim.

Restricții și precizări

• $1 \leq N,Q, t_i \leq 10^5$
• Acest link vă poate fi util în rezolvarea problemei.
• $1 \leq p_i \leq 10^9$
• Valorile din vectorul $t$ sunt distincte două câte două!!

Exemplul 1

stdin

4 3
12 5 4 10
6 7 1 2
1 3
2 4
3 4

stdout

13
15
13

Exemplul 2

stdin

5 5
2 4 6 5 9 
4 9 5 2 8 
2 5
1 2
2 3
2 2
3 3

stdout

0
2
5
4
6