Playing with coins - Problems - Playing with coins - Problems

Coins in denominations of one penny decomposed into stacks (a stack may be a different number of coins), and the stack placed on the table in a row from left to right. Two opponents take turns making moves. Progress lies in the fact that one player takes on the left several piles in a row, no less than one nor more than before that he took his opponent. The first player takes his first move no more than K stacks. The game ends when the cups are left. Required to find the maximum number of coins that can get the first party after the game, if the second player also tries to walk, so to get as many coins.

Input

The first line is a first number of stacks N, follow him: for N numbers giving the number of coins in the stacks from left to right, then the number of K. All the numbers in the row are separated by spaces.

1 <= N <= 180, 1 <= K <= 80, number of coins in the pile - at least 1 and not more than 20 000.

Output

Derive a single number - the maximum number of coins that can certainly get the first player.

Time limit 1 second

Memory limit 64 MiB

Input example

Sample 1
3  4 9 1  3

Sample 2
4  1 2 2 7  3

Sample 3
5  3 4 8 1 7  2

Output example

Sample 1
14

Sample 2
5

Sample 3
18

Show problem classification