Playing with coins#657
Coins of one penny are arranged in stacks (each stack may contain a different number of coins), and these stacks are placed in a row from left to right on the table. Two opponents take turns making moves. On their turn, a player takes at least one consecutive stack from the left, but no more than the number of stacks taken by the opponent in the previous turn. The first player, in their first turn, may take no more than stacks. The game continues until no stacks remain. Find the maximum number of coins the first player can collect, assuming the second player also acts to collect as many coins as possible.
The first line contains the number of stacks , followed by integers denoting the number of coins in each stack from left to right, followed by the number . All numbers are separated by spaces.
1 \leq N \leq 180, 1 \leq K \leq 80, the number of coins in each stack is at least and at most .
Output one number: the maximum number of coins that the first player can guarantee to collect.
Example 1