Prefix Modification Maximum Query

You are given a sequence \(a_1, a_2, \dots, a_n\) initially all zeros. You are also given a sequence of operations \((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\). Operation \((x, y)\) means that you add \(y\) to every element in the prefix \(a_1, a_2, \dots, a_x\).

Then, you need to answer \(m\) queries. Each query is given as two integers \(l\) and \(r\). For a query \((l, r)\), you should apply the operations \((x_l, y_l), (x_{l+1}, y_{l+1}), \dots, (x_r, y_r)\) sequentially (starting from an array of all zeros) and then output the maximum value in the final array \(a_1, a_2, \dots, a_n\), i.e., compute \(\max_{1 \le i \le n}a_i\).

Note: It is guaranteed that every test case has at least 3 queries.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of operations and \(m\) is the number of queries.

The next \(n\) lines each contain two integers \(x_i\) and \(y_i\) describing the \(i\)th operation.

The following \(m\) lines each contain two integers \(l\) and \(r\), representing a query.

outputFormat

For each query, output a single line containing the maximum value in the sequence after applying the specified operations.

sample

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

8
3
3