← 返回题目列表

Codeforces · 461/A

A. Appleman 和 Toastman

中文机器翻译题面 查看原题

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 添加到分数中。这是最佳的行动顺序。