题目描述

光头强想修理熊舍周围的一小段围栏。他测量了围栏，发现他需要 $N(1≤N≤20000)$ 块木板，每块木板都有一定的整数长度 $L_i(1≤L_i≤50000)$ 单位。然后，他购买了一块长度刚好足以锯出 $N$ 块木板的长木板（即，其长度为 $\sum L_i$）。光头强忽略了切损，即锯切时损失的少量长度。

光头强突然发现他没有锯木头的锯子（被熊抢走了），于是他拿着这块长木板来到灰太狼的老家，礼貌地问他是否可以借一把锯子。

灰太狼非常吝啬，他不想免费借给光头强锯子，而要求每锯一次都收一次费。费用为切割木板的总长度。比如，切割总长度为 $15$ 的木板需要 $15$ 元。

光头强知道，他可以按照不同的顺序切割木板，这将导致不同的费用，因为产生的中间木板长度不同。光头强可以自行决定切割木板的顺序和位置。请你帮助光头强确定他可以花多少钱来制作 $N$ 块木板。

输入描述

第 $1$ 行：一个整数 $N$，木板的数量。

第 $2..N+1$ 行：每行包含一个整数，描述所需木板的长度。

输出描述

第 $1$ 行：一个整数：他必须花费 $N-1$ 次削减的最低金额。

3
8
5
8

34

提示

他想把一块长度为 $21$ 的木板切成长度为 $8,5,8$ 的三块。

原始板的尺寸为 $8+5+8=21$。第一次切割将花费 $21$ 元，将板材切割成尺寸为 $13$ 和 $8$ 的两块。第二次切割将花费 $13$，将 $13$ 切割成 $8$ 和 $5$。总共花费 $21+13=34$。如果将 $21$ 切割成 $16$ 和 $5$，第二次切割将花费 $16$，总共 $37$（超过 $34$）。