318009 - 合并石子2

【题目描述】18.9 合并石子2 (merge2)

N堆石子围成一圈,现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序读入堆数N及每堆石子数,使得:

(1)选择一种合并石子的方案,使得N-1次合并后,得分的总和最少;

(2)选择一种合并石子的方案,使得N-1次合并后,得分的总和最大。

输入

第一行为石子堆数N(N≤2500)

第二行为每堆石子数(≤2^{16}),每两个数之间用一空格分隔。

输出

输出两个数,即最小合并数总和及最大合并数总和。

样例

输入

4
4 5 9 4 

输出

43
54

提示

对于50\%的数据,N\leq 100,每堆石子数(≤20)

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题