57. 艾梅洛閣下II世

艾梅洛閣下II世

艾梅洛閣下II世參加完聖杯戰爭後，雖然僥倖存活，但也因此積欠了龐大的債務，因此為了拯救他的名譽，艾梅洛閣下II世要修復他死去的恩師殘留下來破碎的魔術刻印。

下面是債主之一的肖像

因為艾梅洛閣下II世已經沒有太多的積蓄，然而現在有 $n$ 個破碎的魔術刻印等待修復，每個碎片都有不同的大小。最終的目標是要把這些碎片合而為一，而每次施展魔術修復只能能將兩個大小分別為 $a,b$ 的碎片，合併成一個大小為 $a+b$ 的碎片，但是施展魔術需要花費 $a+b$ 單位的魔術催化劑。

因為購買魔術催化劑對於貧窮的艾梅洛閣下II世是一個沉重的負擔，不過不同的修復順序似乎花費的魔術催化劑數量不太一樣，你能幫忙艾梅洛閣下II世找出要花費魔術催化劑最少的修復方法嗎？

輸入

有多筆測資，但不超過 $10$ 筆。

每筆測資第一行有一個數字 $n$，表示魔術刻印的數量，如果 $n=0$ 則結束程式。 接下來下一行有 $n$ 個數字，分別為刻印的大小 $m_1, m_2, \cdots , m_n$。

輸出

對於每一筆測資，輸出艾梅洛閣下II世最少要花費的魔術催化劑數量。

條件限制

對於所有測資：

• $n\leq 500000$
• $m_i \geq m_j$ 對於所有 $i<j$，即輸入的刻印是非嚴格遞減的
• $1\leq m_i \leq 10000$

對於部分測資

• 0% 等同範例
• 20% $n\leq 100$
• 60% $n\leq 10^5$
• 20% 沒有限制

範例輸入1

3
3 2 1
0

範例輸出1

9

範例輸入2

4
4 3 2 1
0

範例輸出2

19

提示

• 第一筆測資，可以先合併 $1,2$ 變成大小 $3$ 的碎片，再與另一個大小 $3$ 的碎片合併，變成大小為$6$，所以總花費是 $3+6=9$。
• 第二筆測資，可以先合併 $1,2$ 變成大小 $3$ 的碎片，再合併 $3,3$ 變成大小為 $6$，再合併 $6,4$ 變成大小為 $10$，最後將所有碎片合併，所以總花費是 $3+6+10=19$。
• 很容易在網路上找到很像的題目，但是解法不會過最後一個測資，請仔細思考題目增加的條件。

Judge Setting

run-time limit: 1200 ms
memory limit: 10485760 byte
測資數量: 22