最小合并成本

难度：T4

【知识点：堆并查集与STL迁移】

前置知识：堆并查集与STL迁移及其冻结前置单元。

题目描述与输入

输入$n$及$n$个非负重量。每次取两份合并，支付两份重量之和，新重量重新参与，直到一份。

输出

输出最小总成本。

数据范围

$1$<=$n<=2000$；$0$<=重量<=$10^6$。

样例输入

4
1 2 3 4

样例输出

19

样例说明

每次取最小两份合并，新重量再次进入候选。请按输入操作顺序逐步核对；没有规定输出的更新操作不输出额外内容。