测试数据来自 system/1176

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　设有 \(n\) 堆石子排成一排，每堆石子的重量用：\(a_1、a_2、…、a_n\)表示，现将这 \(n\) 堆石子归并成一堆，归并的规则：
　　◆每次只能将相邻两堆归并成一堆。
　　◆每次归并的代价是两堆石子的重量之和。
　　例如：假设有这样 7 堆石子，各堆石子的重量分别是：13、7、8、16、21、4、18，将它们归并成一堆有多种归并方法，下图表示了其中两种归并方法：
　　　　
　　图\(a\)所示归并方式的总代价为：20 + 24 + 25 + 44 + 69 + 87 = 269
　　图\(b\)所示归并方式的总代价为：15 + 27 + 22 + 28 + 59 + 87 = 238
　　由此可见，不同的归并方式所得到的总代价是不一样的。那么当给出了 \(n\) 堆石子的重量之后，请你求出最小的总代价和最大总代价。

【输入格式】

　　第一行一个整数 \(n\) ，表示有 \(N\) 堆石子；
　　接下来的 \(N\) 行，每行一个整数，第 \(i+1\) 行表示第 \(i\) 堆石子的重量 \(a_i\)。

【输出格式】

　　第一行一个整数，表示最小总代价；
　　第二行一个整数，表示最大总代价；

【输入输出样例】

　Input

4
7
6
5
6

　Output

48
55

【数据限制】

　　\(n<=100\)
　　每堆石子的数量不超过1000。

【来源】

　　Mr.he