404026 - 修补栅栏

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

Input

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

Output

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

Examples

Input

3
8
5
8

Output

34

Hint

先从无限长的木板上锯下长度为 21 的木板，花费 21； 再从长度为21的木板上锯下长度为5的木板，花费5； 再从长度为16的木板上锯下长度为8的木板，花费8； 总花费＝21＋5＋8＝34

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题