← 返回题目列表

AtCoder · abc270_d

G. 石头

中文机器翻译题面 查看原题

分数: 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