404026 - 修补栅栏

院长家后花园的栅栏坏了,他测量了栅栏,发现需要N(1≤N≤20 000)块木板,每块木板为长度Li(1≤Li≤50 000)的整数。他买了一块长得足以锯成N块木板的长板(也就是说,它的长度是长度Li的总和,不考虑锯木板时的额外损失)。 但是锯木板的代价正好等于它的长度,例如锯一块长度为21的木板要花费的代价为21。问如何安排锯木板的顺序,使得花费的总代价最小。

输入

第一行为一个整数N。随后N行,每行一个整数,代表每块木板长度。

输出

输出一个数,即最小代价。

样例

输入

3
8
5
8

输出

34

提示

先从无限长的木板上锯下长度为 21 的木板,花费 21; 再从长度为21的木板上锯下长度为5的木板,花费5; 再从长度为16的木板上锯下长度为8的木板,花费8; 总花费=21+5+8=34

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题