Cookies#2633
Once, Barash decided to treat Nyusha to some oatmeal cookies. Nyusha was delighted and suggested they divide the cookies as fairly as possible. Barash had cookies, and while it seemed logical to split them evenly, the cookies varied in weight.
Nyusha proposed a game to decide the division. The game consists of rounds, where each player takes one cookie per round in a specific order. In the first round, Nyusha picks a cookie first. After each round, Barash and Nyusha weigh their selected cookies. The player with the lighter total weight at the end of the round picks first in the next round. If their weights are equal, the order remains unchanged.
Although both players will end up with the same number of cookies, the total weight of their cookies might differ. Nyusha wants you to determine the maximum total weight of cookies she can ensure for herself, regardless of Barash's choices.
The first line of the input contains a single number (1 \leq n \leq 7) — the number of cookies each player will have by the end of the game.
The second line contains natural numbers a_i (1 \leq a_i \leq 100) — the weights of the cookies in grams, presented in non-decreasing order.
Output a single number — the maximum total weight of cookies that Nyusha can guarantee to collect.
Example 1