岳不群的併派問題 (AP325 P-4-7)

江湖上門派林立，華山派掌門岳不群認為要消除門派的衝突就是要合併各門派，但不能操之過急，必須每次挑兩個門派合併，如此逐步合併，最後將所有門派合併成一派。合併門派需要一些成本，每個門派都有他的成員數，第 \(i\) 個門派的成員數是 \(m(i)\)，合併兩派的成本就是雙方成員數之和，而兩派合併後，雙方成員就會歸到新合併的門派。岳不群不希望耗費太多成本，輸入各派人數，請幫他計算最少的合併總成本。

舉例來說，一開始如果有三派，\(m = (3, 5, 1)\)，若 \(3\) 人與 \(5\) 人的兩派先合併，成本是 \(3 + 5 = 8\)，合併後剩下兩派，人數是 \((8, 1)\)，再合併這兩派，成本是 \(8 + 1 = 9\)，此時已經只剩下一派，也就是完成所有合併統一江湖了，總成本是 \(8 + 9 = 17\)。如果我們更換合併的順序，先合併 \(3\) 人與 \(1\) 人的兩派（成本 \(4\)），再合併剩下的 \(5\) 人（成本 \(4 + 5 = 9\)），則總成本只有 \(4 + 9 = 13\)。這是這個例子的最低成本。

輸入格式

第一行是一個正整數 \(n\)，代表初始的門派數量；第二行有 \(n\) 個正整數是每派的成員數，同行數字間以空白間隔。

限制

• \(1 \le n \le 2 \times 10^5\)。
• 每個門派的初始人數都是不超過 \(10^5\) 的正整數。

輸出格式

第一行輸出總人數，第二行輸出最小的合併總成本。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

3
3 5 1

範例輸出

9
13

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 4 章 P-4-7，第 122 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。