当前没有测试数据。

D - 石头

得分：400 分

问题描述

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

开始时有一堆包含 $N$ 个石子。两个玩家轮流执行以下操作，高桥先开始。

• 选择一个 $A_i$，它小于等于当前堆中的石子数。从堆中移除 $A_i$ 个石子。

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

如果两个玩家都试图在游戏结束之前最大化他们取走的石子总数，高桥会取走多少石子？

约束

• $1 \leq N \leq 10^4$
• $1 \leq K \leq 100$
• $1 = A_1 < A_2 < \ldots < A_K \leq N$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出：

$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