题目描述

高桥和青木将玩一个取石子的游戏，使用一个序列 $(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$

输出结果。

样例

样例输入 1

10 2
1 4

样例输出 1

5

以下是游戏可能的进展情况之一。

• 高桥从堆中移除 $4$ 个石子。
• 青木从堆中移除 $4$ 个石子。
• 高桥从堆中移除 $1$ 个石子。
• 青木从堆中移除 $1$ 个石子。

在这种情况下，高桥移除了 $5$ 个石子。他无法移除 $6$ 个或更多的石子，所以这是最大值。

以下是另一个可能的游戏进度，高桥移除了 $5$ 个石子。

• 高桥从堆中移除 $1$ 个石子。
• 青木从堆中移除 $4$ 个石子。
• 高桥从堆中移除 $4$ 个石子。
• 青木从堆中移除 $1$ 个石子。

样例输入 2

11 4
1 2 3 6

样例输出 2

8

以下是游戏可能的进展情况之一。

• 高桥从堆中移除 $6$ 个石子。
• 青木从堆中移除 $3$ 个石子。
• 高桥从堆中移除 $2$ 个石子。

在这种情况下，高桥移除了 $8$ 个石子。他无法移除 $9$ 个或更多的石子，所以这是最大值。

样例输入 3

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

样例输出 3

5136