该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P2988 [USACO10MAR] Test Taking S

题目描述

Farmer John 要参加一年一度的农民资格考试。考试很简单，只有 $N$ 个 ( $1≤N≤1,000,000$ ) True/False 的判断题。然而 FJ 去年考试却“杯具”了，Bessie：希望今年能帮帮他。

Bessie 得到可靠的内部消息，有可能有 $T_1$ , $T_2$ , $T_3$ , $\dots$ , 或 $T_K$ ( $0≤T_i≤N$；$0≤K≤10，000$ ) 道题的答案为 ture，但具体哪道题的答案是什么却不知道。Bessie 希望知道在认真研究了这些内部消息后(虽然不能确定任何一道题的具体答案)，一定保证 FJ 考试时能获得的最高分数是多少?

为了说明 Bessie 的想法，考虑 $N=6$ 的一次考试，Bessie 知道答案为 True 的题的数量是 $0$ 或者 $3$。FJ 可以按这样的做题策略来答对至少 $3$ 题：如果 FJ 全部答 'False'，那么当有 $0$ 道题的正确答案是 'True'，则 FJ 答对 $6$ 题；而当有 $3$ 道题的正确答案是 'True'，则 FJ 答对 $3$ 题。因此，只要 FJ 不答 'False'，那么至少一定能答对 $3$ 题，尽管 FJ 并不知道每道题的确切答案。

另一方面，考虑如果 FJ 选择了另一种非最优的做题策略：他猜测某 $3$ 道题为 'True' 而另 $3$ 道题为 'False'。当所有题目的正确答案是 'False' 时，那么 FJ 能答对 $3$ 道题。而当有 $3$ 道题的正确答案是 'True' 时，那么 FJ 有可能一道题都答不对。这是因为 FJ 有可能把 $3$ 道正确答案为 'True' 的题全猜成 'False' !这说明这种做题策略不如前一种优秀。

给出 Bessie 获得的内部消息，计算出 FJ 采用最优做题策略保证能得到的最高分数是多少?

输入格式

第 $1$ 行：$2$ 个整数 $N$，$K$

第 $2,\dots,K+1$ 行：第 $i+1$ 行包含一个整数 $t\_i$

输出格式

第 $1$ 行：一个整数，表示 FJ 一定能获得的最高分数

输入输出样例 #1

输入 #1

6 2 
0 
3

输出 #1

3

说明/提示

翻译提供： @fan404