USACO

USACO 2025 February Contest, Platinum

Problem 3. True or False Test

Contest has ended.

Log in to allow submissions in analysis mode

**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:

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

Contest has ended. No further submissions allowed.