*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).

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.

Problem credits: Benjamin Qi

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

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.

The answer for each \(k\) on a separate line.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > February > Platinum