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.
INPUT FORMAT (input arrives from the terminal / stdin):
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 (print output to the terminal / stdout):
The answer for each k on a separate line.
SAMPLE INPUT:
2 3
3 1
4 2
2
1
0
SAMPLE OUTPUT:
-3
1
7
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
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
