Guaranteed Score in a Modified True/False Exam

Bessie is taking an exam with \(N\) true/false questions. For the \(i\)th question, if she answers correctly, she obtains \(a_i\) points; if she answers incorrectly, she loses \(b_i\) points; and if she leaves it unanswered, her score remains unchanged. All scores satisfy \(0 < a_i, b_i \le 10^9\) and \(1 \le N \le 2\cdot10^5\).

Bessie knows all the correct answers, but she is worried that Elsie, the examiner, may retrospectively change up to \(k\) questions (\(0\le k\le N\)), forcing Bessie to receive a wrong answer on those questions. In other words, if Bessie chooses to answer a set \(S\) of questions, then in the worst case Elsie will pick \(k\) questions from \(S\) (the ones which cause the maximum detriment) and change them. In an answered question the final score becomes:

[ \text{score}_i=\begin{cases} a_i, & \text{if not changed},\ -b_i, & \text{if changed}. \end{cases} ]

Thus, if Bessie answers a set \(S\), her worst-case total score is

[ \sum_{i\in S}{a_i} - \sum_{i\in T}(a_i+b_i), ]

where \(T\subseteq S\) is any subset of answered questions of size at most \(k\) (Elsie will choose the \(k\) questions with the largest \(a_i+b_i\) in \(S\)).

Furthermore, Bessie is required to answer at least \(k\) questions. Given \(Q\) candidate values of \(k\) (with \(1 \le Q \le N+1\)), for each candidate value, determine the maximum score Bessie can guarantee (i.e. maximize the minimum possible score) by choosing a set of questions to answer optimally.

Note: The time limit for this problem is 3 seconds (typically 1.5× the usual limit) and the memory limit is 512 MB (typically 2× the usual limit).

inputFormat

The first line contains two integers \(N\) and \(Q\): the number of questions and the number of candidate values for \(k\). Each of the next \(N\) lines contains two integers \(a_i\) and \(b_i\). Then \(Q\) lines follow, each containing an integer \(k\).

It is guaranteed that \(1 \le N \le 2\cdot10^5\), \(0 \le k \le N\), and \(1 \le Q \le N+1\).

outputFormat

For each candidate \(k\) (in the order given), output a single integer – the maximum guaranteed total score Bessie can achieve if she answers at least \(k\) questions, assuming Elsie changes the answers of at most \(k\) of them (in the worst possible way).

sample

3 3
1 1
2 1
3 2
0
1
2

6
1
-2