Problem Description

There are $ N $ cards, and the $i\ (1\ ≦\ i\ ≦\ N)$ card has an integer $ A_i $ written on it. The game-loving siblings are trying to use these cards to play a game.

• Initially, all cards are placed on the table with the integers visible.
• Each player, on their turn, selects exactly one card from the cards on the table and takes it.
• Turns are taken alternately until there are no cards left on the table.
• The sum of the integers on the cards each player has taken is their score.

When both players try to maximize their scores, what will be the score of the first player?

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 1000)$, representing the number of cards.
• The second line contains $ N $ integers separated by spaces, where the $i\ (1\ ≦\ i\ ≦\ N)$ integer $A_i\ (1\ ≦\ A_i\ ≦\ 1000)$ represents the integer written on the $ i $ card.

Output Format

Output the score of the first player on one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

2
400 628

Sample Output #1

628

Sample Input #2

5
2 5 9 6 5

Sample Output #2

16

Notes/Hints

Sample Explanation 1

In this example, the game proceeds as follows:
- The first player takes the second card.
- The second player takes the first card.
At this point, the first player's score is $ 628 $ and the second player's score is $ 400 $.

Sample Explanation 2

In this example, the game proceeds as follows:
- The first player takes the third card.
- The second player takes the fourth card.
- The first player takes the second card.
- The second player takes the fifth card.
- The first player takes the first card.
At this point, the first player's score is $ 16 $ and the second player's score is $ 11 $.

见题面 Input 部分

见题面 Output 部分