题目描述

数列 $(A_1,\ldots,A_K)$ を使って、高橋君と青木君が石取りゲームをします。

最初、山には $N$ 個の石があります。高橋君から順に、二人が交互に次の操作を行います。

• 現在山にある石の個数以下であるような $A_i$ を $1$ つ選ぶ。山から $A_i$ 個の石を取り除く。

山から石がなくなったとき、ゲームは終了します。

二人がともに、ゲーム終了までに自分が取り除いた石の個数を最大化しようとするとき、高橋君は何個の石を取り除くことができますか？

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_K$

输出格式

答えを出力せよ。

题目大意

题目翻译

Takahashi 和 Aoki 在玩一个取石子的游戏。

刚开始，有 $N$ 个石子，还有一个长度为 $K$ 的序列 $A = \{A_1,A_2,\cdots,A_K\}$。

现在，他们要按照以下规则轮流取石子：

• 对于每次操作，他可以选择一个 $i$（$1 \leq i \leq K$），这时他会取走 $A_i$ 块石子。

• 当一个人没法取石子时，游戏结束。

现在，Takahashi 先取石子，Aoki 后取石子。 他们都想尽可能的最大化他们自己取走的石子数量。

若他们都以最优策略取石子，最后 Takahashi 会取走多少块石子？

输入格式

第一行两个正整数 $N, K$

第二行有 $K$ 个正整数，其中第 $i$ 个表示 $A_i$

输出格式

一行一个正整数，表示若他们都以最优策略取石子，最后 Takahashi 取走的石子数量。

数据范围

对于 $100\%$ 的数据，保证：

• $1 \leq N \leq 10^4$
• $1 \leq K \leq 100$
• $1 = A_1 < A_2 < \cdots < A_K \leq N$

10 2
1 4

5

11 4
1 2 3 6

8

10000 10
1 2 4 8 16 32 64 128 256 512

5136

提示

制約

• $1\ \leq\ N\ \leq\ 10^4$
• $1\ \leq\ K\ \leq\ 100$
• $1\ =\ A_1\ <\ A_2\ <\ \ldots\ <\ A_K\ \leq\ N$
• 入力に含まれる値は全て整数である

Sample Explanation 1

ゲームの進行の一例は以下の通りです。 - 高橋君が山から $4$ 個の石を取り除く。 - 青木君が山から $4$ 個の石を取り除く。 - 高橋君が山から $1$ 個の石を取り除く。 - 青木君が山から $1$ 個の石を取り除く。 この例では高橋君は $5$ 個の石を取り除くことができます。高橋君が $6$ 個以上の石を取り除くことはできないためこれが最大です。 高橋君は $5$ 個の石を取り除くことができるゲームの進行の例には、他にも次のようなものがあります。 - 高橋君が山から $1$ 個の石を取り除く。 - 青木君が山から $4$ 個の石を取り除く。 - 高橋君が山から $4$ 個の石を取り除く。 - 青木君が山から $1$ 個の石を取り除く。

Sample Explanation 2

ゲームの進行の一例は以下の通りです。 - 高橋君が山から $6$ 個の石を取り除く。 - 青木君が山から $3$ 個の石を取り除く。 - 高橋君が山から $2$ 個の石を取り除く。 この例では高橋君は $8$ 個の石を取り除くことができます。高橋君が $9$ 個以上の石を取り除くことはできないためこれが最大です。