/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
数列 (A_1,\ldots,A_K) を使って、高橋君と青木君が石取りゲームをします。
最初、山には N 個の石があります。高橋君から順に、二人が交互に次の操作を行います。
- 現在山にある石の個数以下であるような A_i を 1 つ選ぶ。山から 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
Score : 400 points
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