Maximizing the Minimum Sum in Subsequence Selection

Given a sequence of n integer pairs \((x_i, y_i)\), and m queries. For each query, you are given two integers \(a\) and \(b\). You need to choose an integer \(k\) (note that \(k\) can be 0), and then select a strictly increasing sequence of indices \(1 \le p_1 < p_2 < \cdots < p_k \le n\) (if \(k = 0\) then the sequence is empty), so that

\[ \min\Bigl(a + \sum_{i = 1}^{k} x_{p_i},\; b + \sum_{i = 1}^{k} y_{p_i}\Bigr) \]

is maximized. Output this maximum value for each query.

inputFormat

The first line contains two integers \(n\) and \(m\).

The following \(n\) lines each contain two integers \(x_i\) and \(y_i\).

Each of the next \(m\) lines contains two integers \(a\) and \(b\) representing a query.

outputFormat

For each query, output one line containing the maximum value that can be achieved.

sample

3 3
1 2
2 1
-1 3
0 0
1 1
-2 -1

5
6
3