我们的目标是将一块完整的木板切割成 $n$ 块，每块长度为 $L_1, L_2, L_3 ... L_n$。切割后各个木块的长度总和与切割前的木板长度相等。

每次在一块木板上切一刀，代价等于该木板的长度。例如：

• 在长度为 $21$ 的木板切一刀，变成两块木板，长度分别为 $5,16$，所需代价为 $21$
• 在长度为 $16$ 的木板上再切一刀，变为两块木板，长度分别为 $8, 8$，所需代价为 $16$

为了达到上述目标，求最小的切割代价是多少。

输入

• 第一行是整数 $n(1 \leq n \leq 20000)$，表示要将原始木板切割成多少块
• 接下来 $n$ 行，每行一个整数，表示最终每块小木板的长度，其中 $1 \leq L_i \leq 50000$

输出

• 一行，一个整数，表示达到目标所需的最小代价

提示

• 2021/12/07 测试数据更新，以往通过代码不会重判，可尝试重新提交