True or False Test
**Note: The time limit for this problem is 3s, 1.5x the default. The memory limit for this problem is 512MB, twice the default.**
Bessie is taking an N-question true or false test (1≤N≤2⋅105). For the i-th question, she will gain ai points if she gets it correct, lose bi points if she gets it incorrect, or remain even if she does not answer it (0<ai,bi≤109).
Bessie knows all the answers because she is a smart cow, but worries that Elsie (who is administering the test) will retroactively change up to k of the questions after the test such that Bessie does not get those questions correct.
Given Q (1≤Q≤N+1) candidate values of k (0≤k≤N), determine the number of points Bessie can guarantee for each k, given that she must answer at least k questions.
For each value of k, it is optimal for Bessie to answer all of the questions.
SCORING:
- Inputs 2-4: N≤100
- Inputs 5-7: Q≤10, N≤2⋅105
- Inputs 7-20: No additional constraints.
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The first line contains N and Q.
The next N lines each contain ai and bi.
The next Q lines each contain a value of k. No value of k appears more than once.
Output Format
The answer for each k on a separate line.