Cookies
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 2n 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 n 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.
Input
The first line of the input contains a single number n (1 ≤ n ≤ 7) - the number of cookies each player will have by the end of the game.
The second line contains 2n natural numbers a_i (1 ≤ a_i ≤ 100) - the weights of the cookies in grams, presented in non-decreasing order.
Output
Output a single number - the maximum total weight of cookies that Nyusha can guarantee to collect.