RoAlgo Contest #8 | Kiloforces

Vadim is a very talented and passionate young man about computer science. Filled with the Christmas spirit, he decides to spend his winter vacation participating in as many contests as possible on his favorite platform, $\text{Kiloforces}$. There, the scoring system is a bit different. If the contest has $K$ problems, with the $i$-th problem worth $p_i$ points, then when he solves problem $j$, $p_j$ points are added to his total score, and $t_j$ points are subtracted from the scores of the unsolved problems. The platform rules allow for there to be problems with negative scores at any given time (which Vadim will need to solve).

Task

Vadim receives $N$ problems, knowing the values $p_i$ and $t_i$ for each. Over the next $Q$ days, he chooses an interval $[l, r]$ and wonders what the maximum score he can achieve is if he participates in a contest consisting of problems $l, l+1, l+2, \dots, r-1, r$. Help Vadim answer these $Q$ questions, or else you will end up on Santa's naughty list.

Input data

The first line contains $N$ and $Q$. The next 2 lines will each contain $N$ values ($p_i$ and $t_i$), and the last $Q$ lines contain the questions posed by Vadim.

Output data

Each of the next $Q$ lines will contain the answers to Vadim's questions.

Constraints and clarifications

• $1 \leq N,Q, t_i \leq 10^5$
• This link might be helpful in solving the problem.
• $1 \leq p_i \leq 10^9$
• The values in array $t$ are pairwise distinct!!

Example 1

stdin

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

stdout

13
15
13

Example 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