Stones

AtCoder

IDabc270_d

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

10 2
1 4

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.

Input #2

11 4
1 2 3 6

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.

Input #3

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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Stones",
    "description": {
      "content": "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 o",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc270_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi and Aoki will play a game of taking stones using a sequence $(A_1, \\ldots, A_K)$.\nThere is a pile that initially contains $N$ stones. The two players will alternately perform the following o...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments