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

• 3 \le n \le 10^5
• 1 \le c_k \le 10^6

Examples

Input:

6
2 1 5 3 4 3

Output:

10

Input:

5
1 2 5 4 3

Output:

7