Code Submission Evaluation System Login

CSES - HIIT Open 2016 Practice

HIIT Open 2016 Practice

Contest start:2016-05-19 17:00:00
Contest end:2016-05-28 9:00:00

Task list | Submit code | Submissions | Scoreboard | Statistics


Card game

Time limit:1.00 s
Memory limit:128 MB

Uolevi and Maija are playing a game with $n$ cards. Each of the cards has a number written on it. Uolevi tries to maximize the sum of numbers of cards he gets and Maija tries to maximize the sum of numbers of cards she gets.

At the beginning of the game all cards are on a table so that both Uolevi and Maija can see them and the numbers on them. In a single move, Uolevi chooses any three of the remaining cards on the table. Then Maija chooses one of the cards Uolevi chose, and takes it to herself. Uolevi takes the other two cards. This continues until there are less than three cards left. Maija gets the remaining cards. What is the sum of numbers of cards Uolevi gets if they both play optimally?

Input

The first line contains one integer $n$, the number of cards.

The second line contains $n$ integers $c_1,c_2,\ldots,c_n$, the numbers written on the cards.

Output

Output a single integer, the sum of numbers of cards Uolevi gets if they both play optimally.

Constraints
Examples

Input:
6
2 1 5 3 4 3


Output:
10

Input:
5
1 2 5 4 3


Output:
7