Appleman 和 Toastman 玩游戏。最初Appleman给Toastman一组n个数字,然后他们开始完成以下任务:
- 每次 Toastman 获得一组数字时,他都会将所有数字相加,并将总和添加到分数中。然后他把这个组交给了苹果人。
- 每次 Appleman 得到一个由单个数字组成的组时,他都会将该组扔掉。每次 Appleman 得到一个由多个数字组成的组时,他都会将该组分成两个非空组(他可以用任何方式做到这一点),并将它们分别交给 Toastman。
当人们完成所有任务后,他们会查看分数值。他们可以获得的最大可能分数是多少?
输入
第一行包含一个整数 n (1 ≤ n ≤ 3·105)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 106) — 赋予 Toastman 的初始组。
输出
打印一个整数——最大可能分数。
示例
输入 #1
3 3 1 5
输出 #1
26
输入 #2
1 10
输出 #2
10
注意
在第一个示例中考虑以下情况。最初,Toastman 获得组 [3, 1, 5] 并将分数加 9,然后将该组交给 Appleman。 Appleman 将组 [3, 1, 5] 分为两组:[3, 5] 和 [1]。两者都应该给 Toastman。当 Toastman 收到组 [1] 时,他将得分加 1 并将该组交给 Appleman(他会将其扔掉)。当 Toastman 收到组 [3, 5] 时,他将分数加 8 并将该组交给 Appleman。 Appleman 以唯一可能的方式拆分 [3, 5]:[5] 和 [3]。然后他将这两个组都交给 Toastman。当 Toastman 收到 [5] 时,他将分数加 5 并将该组交给 Appleman(他会将其扔掉)。当 Toastman 收到 [3] 时,他将分数加 3 并将该组交给 Appleman(他会将其扔掉)。最后,Toastman 将 9 + 1 + 8 + 5 + 3 = 26 添加到分数中。这是最佳的行动顺序。