取石子

题目描述

高桥和青木将使用序列 $(A_1, \ldots, A_K)$ 玩一个取石子的游戏。

有一个初始包含 $N$ 颗石子的堆。两名玩家将交替执行以下操作,高桥先手。

选择不超过当前堆中石子数的 $A_i$,从堆中移除 $A_i$ 颗石子。

当堆中没有石子时,游戏结束。

如果两名玩家都试图最大化自己在游戏结束前移除的石子总数,高桥会移除多少颗石子?

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

10 2
1 4

5

下面是游戏的一种可能进程。

高桥从堆中移除 $4$ 颗石子。

青木从堆中移除 $4$ 颗石子。

高桥从堆中移除 $1$ 颗石子。

青木从堆中移除 $1$ 颗石子。

在这种情况下,高桥移除了 $5$ 颗石子。他没有办法移除 $6$ 颗或更多,所以这是最大值。

下面是高桥移除 $5$ 颗石子的另一种可能进程。

高桥从堆中移除 $1$ 颗石子。

青木从堆中移除 $4$ 颗石子。

高桥从堆中移除 $4$ 颗石子。

青木从堆中移除 $1$ 颗石子。

11 4
1 2 3 6

8

下面是游戏的一种可能进程。

高桥移除 $6$ 颗石子。

青木移除 $3$ 颗石子。

高桥移除 $2$ 颗石子。

在这种情况下,高桥移除了 $8$ 颗石子。他没有办法移除 $9$ 颗或更多,所以这是最大值。

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 \lt A_2 \lt \ldots \lt A_K \leq N$
• 输入中的所有值均为整数。