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 Input 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