问题描述 农夫约翰想修补牧场周围的一小段篱笆。他测量后发现需要 $N（1 ≤ N ≤ 20,000）$块木板，每块木板的长度为整数 $Li（1 ≤ Li ≤ 50,000）$。于是他购买了一块足够长的木板，其总长度恰好等于 $N$ 块木板的长度之和（即总长度为 $Li$ 的总和）。假设切割时无需考虑锯口损耗（即忽略锯木屑导致的额外长度损失）。

不幸的是，约翰发现自己没有锯子，于是他带着这块长木板来到农夫唐的农场，礼貌地询问是否可以借用锯子。

农夫唐是个隐藏的 “资本家”，他不直接借锯子，而是要求约翰为长木板的 $N-1$ 次切割付费，每次切割的费用恰好等于被切割木板的长度。例如，切割一块长度为$21$ 的木板需要支付 $21$ 美分。

唐允许约翰自行决定切割的顺序和位置。请帮助约翰计算他将长木板切割成 $N$ 块所需的最小费用。约翰知道，不同的切割顺序会导致中间木板的长度不同，从而产生不同的总费用。

输入格式

第 1 行：一个整数 $N$，表示需要的木板数量

第 2 行到第 $N+1$ 行：每行一个整数，表示每块木板的长度

输出格式

第 1 行：一个整数，表示切割成 N 块木板的最小总费用

输入样例 1

3 8 5 8

输出样例 1

34

样例解释 约翰需要将长度为 $21$ 的木板切割成 $8、5、8$ 三块。 原始木板长度为 $8+5+8=21$。第一次切割费用为 21，将木板切成 $13$ 和 $8$$。 第二次切割费用为 $13$，将 $13$ 切成 $8$ 和 $5$。总费用为 $21+13=34$。 如果第一次切成 $16$ 和 $5$，则第二次切割费用为 $16$，总费用 $37$（比 34 更大）