Problems
Bessie is taking a true-or-false test with N questions (1 ≤ N ≤ 2⋅10⁵). For the i-th question, she earns aᵢ points if she answers correctly, loses bᵢ points if she answers incorrectly, and receives 0 points if she leaves it unanswered (0 < aᵢ, bᵢ ≤ 10⁹).
Bessie knows all the answers, but she is worried that after the test, Elsie—the administrator—might retroactively change up to k of the questions so that Bessie’s answers become incorrect.
For each candidate k (0 ≤ k ≤ N), Bessie must answer at least k questions. Since Elsie can change up to k answers among those Bessie has given, in the worst-case scenario, exactly k answered questions will be marked wrong and the remaining will be correct.
The goal is to maximize the minimum score Bessie can guarantee regardless of which k questions Elsie chooses to change.
It turns out that in this setting, it is optimal for Bessie to answer every question. In that case, for each question i, Bessie would normally earn aᵢ points; however, if Elsie changes that answer, she loses bᵢ points (i.e. she effectively loses aᵢ + bᵢ points compared to a correct answer). Hence, Elsie will choose the k questions with the highest values of (aᵢ + bᵢ) to change.
Thus, the guaranteed score when answering all questions is:
Total score = (∑₁⁽ᴺ⁾ aᵢ) − (sum of the k largest values among (aᵢ + bᵢ)).
Input
The first line contains two integers N and Q, where Q is the number of candidate k values (1 ≤ Q ≤ N+1).
The next N lines each contain two integers aᵢ and bᵢ (0 < aᵢ, bᵢ ≤ 10⁹) for i = 1, 2, …, N.
The following Q lines each contain a candidate value k (0 ≤ k ≤ N), with no candidate value appearing more than once.
Output
For each candidate k, output on a separate line the guaranteed minimum score Bessie can obtain.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 20 | |
| #2 | 30 | |
| #3 | 50 | No additional constraints |
Example
2 3
3 1
4 2
2
1
0
-3
1
7
You must sign in to write code.