题目描述

芯芯最近发明了一款自己设计的小游戏，名字叫——《打包大作战》！她打算带到班级里和小伙伴们一起玩！

游戏的玩法灵感来自她家周末收拾房间时打包旧玩具的经历：她发现，如果每次把两个小包裹打包成一个大包裹，最后就可以把所有东西装进一个超级包裹里啦！

但在游戏中，每次打包两个包裹，都会消耗一定的时间，时间等于这两个包裹的重量之和。芯芯的目标是用最少的时间，把所有包裹打成一个超级包裹！

她想请你帮忙，算一算打包完成最少要用多少时间，她好在游戏中设置最佳成绩！

游戏规则

• 初始有 $N$ 个包裹，每个有一个正整数重量；
• 每次只能选两个包裹打包成一个新包裹，耗时为它们的重量之和；
• 新包裹也可以继续打包；
• 目标是把所有包裹合并成一个；
• 希望总耗时最少。

【输入格式】

• 第一行：一个整数 $N$，表示包裹的数量；
• 第二行：$N$ 个正整数 $a_1, a_2, ..., a_N$，表示每个包裹的重量。

【输出格式】

• 一行一个整数，表示最少总耗时。

4
1 2 3 4

19

数据范围

$1 \leq N \leq 10^5$
$1 \leq a_i \leq 10^4$