说明

时北北学长在一张画布上画了n个点，第 i 个点有一个权值a[i]，连接两个点需要耗费时北北一定的精力，可以使这两个点变成一个，

这个新的点的权值为其组成两点权值之和，这个精力大小为新的点的权值。时北北很懒，他想消耗最少的精力所有点连接变成一个点，但是他不知道该怎么做。

例如，一共有三个点，权值分别为1，2，4，第一次花费3点精力连接第一个点和第二个点，第二次花费7点精力连接第三个点和前两个点。

一共花费10点体力。

你可以帮帮他吗。

输入格式

第1行输入一个数字n(1 ≤ n ≤ 10000)，代表一共有n个点

第2行有n个用空格隔开的数字a[i]（1 ≤ a[i] ≤ 20000），代表第 i 个点的权值

输出格式

输出一个数字x，代表消耗最少的精力。输入数据保证这个值小于2^31

样例

3
1 2 4

10