|Codeforces Round #263 (Div. 1)|
Appleman and Toastman play a game. Initially Appleman gives one group of n numbers to the Toastman, then they start to complete the following tasks:
After guys complete all the tasks they look at the score value. What is the maximum possible value of score they can get?
The first line contains a single integer n (1 ≤ n ≤ 3·105). The second line contains n integers a 1, a 2, ..., a n (1 ≤ a i ≤ 106) — the initial group that is given to Toastman.
Print a single integer — the largest possible score.
3 1 5
Consider the following situation in the first example. Initially Toastman gets group [3, 1, 5] and adds 9 to the score, then he give the group to Appleman. Appleman splits group [3, 1, 5] into two groups: [3, 5] and . Both of them should be given to Toastman. When Toastman receives group , he adds 1 to score and gives the group to Appleman (he will throw it out). When Toastman receives group [3, 5], he adds 8 to the score and gives the group to Appleman. Appleman splits [3, 5] in the only possible way:  and . Then he gives both groups to Toastman. When Toastman receives , he adds 5 to the score and gives the group to Appleman (he will throws it out). When Toastman receives , he adds 3 to the score and gives the group to Appleman (he will throws it out). Finally Toastman have added 9 + 1 + 8 + 5 + 3 = 26 to the score. This is the optimal sequence of actions.