Score : $400$ points

问题描述

Takahashi 和 Aoki 将通过一个序列 $(A_1, \ldots, A_K)$ 进行一场取石子游戏。

初始时，有一堆包含 $N$ 个石子。两位玩家将轮流执行以下操作，由 Takahashi 先手执行：

• 选择一个不超过当前堆中石子数量的 $A_i$，然后从堆中移除 $A_i$ 个石子。

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

如果两名玩家都试图在游戏结束前最大化自己所移除的石子总数，那么 Takahashi 最终会移除多少个石子呢？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi and Aoki will play a game of taking stones using a sequence $(A_1, \ldots, A_K)$.

There is a pile that initially contains $N$ stones. The two players will alternately perform the following operation, with Takahashi going first.

• Choose an $A_i$ that is at most the current number of stones in the pile. Remove $A_i$ stones from the pile.

The game ends when the pile has no stones.

If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?

Constraints

• $1 \leq N \leq 10^4$
• $1 \leq K \leq 100$
• $1 = A_1 < A_2 < \ldots < A_K \leq N$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $A_2$ $\ldots$ $A_K$

Output

Print the answer.

Sample Input 1

10 2
1 4

Sample Output 1

5

Below is one possible progression of the game.

• Takahashi removes $4$ stones from the pile.
• Aoki removes $4$ stones from the pile.
• Takahashi removes $1$ stone from the pile.
• Aoki removes $1$ stone from the pile.

In this case, Takahashi removes $5$ stones. There is no way for him to remove $6$ or more stones, so this is the maximum.

Below is another possible progression of the game where Takahashi removes $5$ stones.

• Takahashi removes $1$ stone from the pile.
• Aoki removes $4$ stones from the pile.
• Takahashi removes $4$ stones from the pile.
• Aoki removes $1$ stone from the pile.

Sample Input 2

11 4
1 2 3 6

Sample Output 2

8

Below is one possible progression of the game.

• Takahashi removes $6$ stones.
• Aoki removes $3$ stones.
• Takahashi removes $2$ stones.

In this case, Takahashi removes $8$ stones. There is no way for him to remove $9$ or more stones, so this is the maximum.

Sample Input 3

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

Sample Output 3

5136

update @ 2024/3/10 11:23:25