Petya loves computer games very much. Recently, he discovered an interesting role-playing game on the Internet. Controlling the hero, you need to look for magical artifacts and get gold.
Unfortunately, the very first quest in the game put Petya in a dead end. After completing the task, he received n magical artifacts that can be used to get gold. For each artifact its value is known, for the i -th artifact it is equal to w
i . Artifacts can be activated to get gold. Each artifact can only be activated once. Petya can activate artifacts in any order.
The hero controlled by Petya has magic power, initially it is equal to zero. There are two ways to activate an artifact: through magic and through force. If you activate an artifact with a value of w using magic, then the hero's magic power is increased by w . If you activate an artifact with a value of w using force, then the hero receives xw gold coins, where x — the hero's magic power at the moment the artifact is activated.
For example, if the hero Petit received 4 artifacts with values 1, 1, 2 and 2, then you can get 9 gold coins by proceeding as follows. First, you need to use magic to activate one artifact each with a value of 1 and 2. After that, the hero's magic power is 3, now you can activate the remaining artifacts using strength and get 3 and 6 gold coins, respectively.
Help Petya determine the maximum number of gold coins he can get by activating the artifacts in the correct order in the best possible way.
Input
The first line of the input contains a single number n — number of magic artifacts ( 1 ≤ n ≤ 100 ).
The second line of the input contains n numbers w
1 , w
2 , ..., w
n — artifact values ( 1 ≤ w
i ≤ 100 ).
Imprint
Print the maximum possible number of gold coins that can be obtained with the help of magical artifacts.
Examples
| # |
Input |
Output |
| 1 |
4
1 1 2 2
| 9 |