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

Given a sequence of operations $(x_1, y_1), \dots, (x_n, y_n)$, an operation $(x, y)$ adds $y$ to the values of $a_1, \dots, a_x$.

There are $m$ queries. Each query provides $l$ and $r$, and asks for the value of $\mathop\max\limits_{i=1}^n a_i$ after performing the operations $(x_l, y_l), \dots, (x_r, y_r)$ sequentially on a sequence $a$ initialized to $0$.

Input

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

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

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

Output

Output $m$ lines, each containing an integer representing the answer to each query.

Examples

Input 1

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

Output 1

19
19
15
15
8