Test Taking

Farmer John must take his annual farming-license test, which has $N$ ($1 \le N \le 1{,}000{,}000$) true/false questions. After a dismal result last year, his cow Bessie wants to help.

Bessie has inside information: the number of questions whose correct answer is 'true' is guaranteed to be one of $t_1, t_2, \dots, t_K$ ($0 \le t_i \le N$; $0 \le K \le 10{,}000$). She does not know the correct answer to any individual question — only the possible totals of 'true' answers.

Farmer John writes an answer ('true' or 'false') for every question. Because he knows nothing about any specific question, an adversary may choose both the actual number of 'true' answers (one of Bessie's values) and exactly which questions those are, so as to make Farmer John's score as low as possible. Farmer John wants to pick his answers so that the number of correct answers he is guaranteed — no matter what — is as large as possible.

For example, take $N = 6$ with the count of 'true' answers being $0$ or $3$. If Farmer John marks every question 'false', he gets all $6$ correct when the count is $0$ and $3$ correct when the count is $3$, so at least $3$ are guaranteed. If instead he guesses that some $3$ answers are 'true', the adversary can make all $3$ of those wrong, dropping his guarantee to $0$. Marking everything 'false' is therefore better, guaranteeing $3$.

Given Bessie's information, determine the largest number of correct answers Farmer John can guarantee by playing optimally.

• Line 1: two space-separated integers $N$ and $K$.
• Lines $2 \dots K+1$: line $i+1$ contains a single integer $t_i$.

(When $K = 0$ there are no further lines.)

• A single integer: the best score Farmer John is guaranteed to achieve.