A94813.abc270D - Stones

问题陈述

高桥和青木将用序列 $(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$

打印答案

样例一解释

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

• 高桥从棋堆中取出 $4$ 颗棋子。
• 青木从棋堆中取出 $4$ 颗棋子。
• 高桥从棋堆中取出 $1$ 颗棋子。
• 青木从棋子堆中取出 $1$ 颗棋子。

在这种情况下，高桥取出了 $5$ 颗棋子。他不可能取出 $6$ 或更多的棋子，因此这是最大值。

下面是对局的另一种可能进展，即高桥取出 $5$ 颗棋子。

• 高桥从棋堆中取出 $1$ 颗棋子。
• 青木从棋堆中取出 $4$ 颗棋子。
• 高桥从棋子堆中取出 $4$ 枚棋子。
• 青木从棋子堆中移除 $1$ 个棋子。

样例二解释

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

• 高桥下出 $6$ 子。
• 青木取出 $3$ 子。
• 高桥移去 $2$ 子。

在这种情况下，高桥移去 $8$ 子。他不可能取出 $9$ 或更多的棋子，因此这是最大值。