P2988 [USACO10MAR] Test Taking S

Farmer John has to take his annual farming license test. The test has $N$ ($1 \le N \le 1{,}000{,}000$) true/false questions. After last year's poor performance, Bessie wants to help him. Bessie knows that the number of questions whose answer is 'true' is one of $t_1, t_2, \dots, t_K$ ($0 \le t_i \le N$; $0 \le K \le 10{,}000$). She has no information about which particular questions are true. Using only this information, she wants to know the best score Farmer John can always guarantee, even without knowing any individual answers. Example: For $N = 6$ and possible counts $\{0, 3\}$, if FJ answers 'false' on every question, then if the true count is $0$ he gets $6$ correct, and if it is $3$ he gets $3$ correct. So he can guarantee at least $3$ correct. By contrast, if FJ answers 'true' on exactly $3$ questions and 'false' on the other $3$, then if the true count is $0$ he gets $3$ correct, but if the true count is $3$ he could get as few as $0$ correct (if he guessed 'true' on the $3$ that are actually 'false'). So this strategy does not guarantee any correct answers. Given Bessie's information, compute the maximum number of answers FJ can always get correct if he uses an optimal strategy. Constraints: $1 \le N \le 1{,}000{,}000$, $0 \le K \le 10{,}000$, $0 \le t_i \le N$.

- Line 1: Two space-separated integers $N$ and $K$. - Lines $2..K+1$: Line $i+1$ contains a single integer $t_i$.

- Line 1: A single integer, the best score FJ is guaranteed to achieve.

Translation provided by @fan404. Translated by ChatGPT 5