Migrated from Lutece 1599 wtmsb

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这天，$AutSky\_JadeK$看到了$n$张图片,他忍不住说道：“我$TM$社保！”。

每张图片有一个社保值，他可以合并两张图片，合并所得的图片的社保值是原来两张图片的社保值之和。
每次合并需要消耗的体力也是原来两张图片的社保值之和。 显然，$n-1$次合并之后，只剩下一张图片。
他想知道，在这个过程中，他消耗的总体力最少是多少。

Input

第一行包含一个整数$n$，
第二行包含$n$个整数$A_1,A_2,{\ldots},A_n$，代表$n$张图片的社保值。

Output

输出一行，包含一个整数，代表他消耗的总体力最少是多少。

Samples

3
1 2 9

15

Note

$1{\leq}n{\leq}20000$，
$1{\leq}A_i{\leq}2000$

Resources

17暑假前集训-数据结构专题 By AutSky_JadeK，思路非原创 - NOIP2004 提高组 合并果子