Problem Description

You need to maintain a sequence $a_1,\dots,a_n$.

You are given an operation sequence $(x_1,y_1),\dots,(x_n,y_n)$. An operation $(x,y)$ means adding $y$ to the values of $a_1,\dots,a_x$.

There are $m$ queries. Each query gives $l,r$ and asks: starting from an initial sequence $a$ where all values are $0$, execute the operations $(x_l,y_l),\dots,(x_r,y_r)$ in order. What is the final value of $\max\limits_{i=1}^n a_i$?

Input Format

The first line contains two integers $n,m$ ($1\le n,m\le 5\times 10^5$).

The next $n$ lines each contain two integers $x_i,y_i$ ($1\le x_i\le n, |y_i|\le n$).

The next $m$ lines each contain two integers $l,r$ ($1\le l\le r\le n$).

Output Format

Output $m$ lines, each containing one integer, which is the answer to each query.

6 5
6 4
2 6
5 -5
3 6
1 2
3 6
1 6
1 6
2 6
2 6
5 6

19
19
15
15
8

Hint

Source and Acknowledgements

From the THUPC2024 (2024 Tsinghua University Student Programming Contest and Intercollegiate Invitational) finals.

For testdata, statement, reference solution, editorial, etc., please refer to the official THUPC repository https://thusaac.com/public.

Translated by ChatGPT 5