platinum_True_or_False_Test (USACO February_Contest)
Time limit: 3 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: data structures, segment tree, divide and conquer, dynamic programming

**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\le N\le 2\cdot 10^5$).
For the $i$-th question, she will gain $a_i$ points if she gets it correct, lose
$b_i$ points if she gets it incorrect, or remain even if she does not answer it
($0<a_i,b_i\le 10^9$).
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\le Q\le N+1$) candidate values of $k$ ($0\le k\le 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 $a_i$ and $b_i$.
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\le 100$
Inputs 5-7: $Q\le 10$,
$N\le 2\cdot 10^5$
Inputs 7-20: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: