Two players, and
, are playing a game on a row of
coins, each with a positive integer value
. Player
goes first and can take any coin. Then, player
must take a coin adjacent to the coin that
chose, or must skip his turn if there are no coins adjacent to the spot that
chose. The players then alternate turns, where
can always take any remaining coin but
must take a coin adjacent to the spot
just chose or skip his turn if this is not possible. The game ends when all the coins are taken by one of the two players. Both players want to maximize the total sum of the values of the coins they have at the end.
The players will play the game times, where after each game all the coins are returned to their original positions in the row and a new coin with value
is added to the right end of the row.
Assuming they play optimally, calculate the total sum that player will get in each game.
Constraints
and
for all
.
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [10%]
Subtask 4 [15%]
Subtask 5 [15%]
Subtask 6 [20%]
Subtask 7 [20%]
Input Specification
The first line contains two space-separated integers: and
.
The second line contains space-separated integers:
.
The third line contains space-separated integers:
.
If , the third line is empty.
Output Specification
Output lines: the total sum that player
will get in each game.
Sample Input 1
5 1
3 1 4 2 5
6
Sample Output 1
12
13
Explanation for Sample Output 1
Here is one way the first game could proceed:
- First, player
takes the coin with a value of
.
- Then, player
must take either the coin with value
or the coin with value
. He decides to take the coin with value
.
- Then, player
takes the coin with value
. There are no untaken coins adjacent to this coin, so player
must skip his turn.
- Finally, player
takes the coin with value
. Player
must take the only remaining coin with value
, and the game ends with
getting a total sum of
.
The second game is played on the row , and player
can get a total sum of
if both players play optimally.
Sample Input 2
10 0
27 18 28 18 28 45 90 45 23 53
Sample Output 2
243
Comments