分数: 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
输出
打印答案。
示例输入 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