2601. 游戏_

【题目描述】

Cindy 和 Dan 在玩一个游戏。初始 Cindy 把 n 个数给 Dan，然后开始游戏：

每次 Dan 得到一组数后，他会把所有的数加起来，然后把总和加入到分数当中。然后他就把这组数给回 Cindy。

每次 Cindy 得到一组数后，如果这组数只有一个，那么她会把它扔掉；如果这组数多于一个，她会把这组数分成两组（每组至少有一个数） ，然后把它们分别给回 Dan。

每次游戏结束后他们特别关心自己的分数。他们想知道对于一组数，能得到的最大的得分是多少？

【输入格式】

第一行一个正整数 n，代表一开始数的个数；

第二行 n 个正整数，代表这 n 个整数是什么。

【输出格式】

一行一个整数，代表可能的最大得分。

【样例输入】

3

3 1 5

【样例输出】

26

【样例解释】

对于样例，一开始 Cindy 把[3, 1, 5]给 Dan，Dan 向总分加上 3 + 1 + 5；Dan把[3, 1, 5]给回 Cindy，Cindy 把它分成两组数[3, 5]和[1]，再给回 Dan，Dan 得到[1]后往总分加上 1 并把[1]给回 Cindy， Cindy 在得到后把它扔掉； Dan 得到[3,5]后往总分加上 3 + 5，再给回 Cindy。Cindy 最后把[3, 5]分成[3]和[5]，Dan 在总分分别加上 3 和 5.最后他们的总分是 9 + 1 + 8 + 3 + 5 = 26.

【数据范围与约定】

对于 30%的数据，N<=5;

对于 60%的数据，N<=1000;

对于 100%的数据，N<=100000;

所有的数权值小于 1000000.

【来源】

清北学堂寒假基础班模拟