Kata

Problem Statement

Alice and Bob are playing a strategic game with a stack of collectible cards, each having a certain value. The rules are as follows:

1. Both players draw at least 1 card in their turn.
2. Alice starts by drawing 1 card.
3. In subsequent turns, both players can draw up to twice the maximum number of cards drawn in any previous turn.
4. Both players aim to maximize their total value of collected cards while playing optimally.

Given the values of all cards, determine the maximum total value of cards Alice can collect.

Input

• values: A list of n integers representing the values of the cards in the stack, from top to bottom.

Constraints

• 1 <= n <= 1000

• 0 <= values[i] <= 10^6

Output

• An integer representing the maximum total value of cards Alice can collect.

Example

Input 1

[10, 20, 30, 20, 50]

Output 1

60

Explanation 1

1. Alice's first turn: Alice draws the top card, which has a value of 10.
2. Bob's first turn: Bob can draw between 1 and 2 cards. He draws 20. His total value is now 20.
3. Alice's second turn: Alice can draw between 1 and 2 cards. She draws 30 and 20. Her total value is now 10 + 30 + 20 = 60.
4. Bob's second turn: Bob can draw between 1 and 4 cards. He draws 50. His total value is now 20 + 50 = 70.

Note that if Bob draws 2 cards at first, Alice will draw 3 cards in her second turn, leaving Bob less final total value of 50.

Input 2

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Output 2

24