题目描述

小熊在田里掰玉米，有一排 N 棵玉米，每棵玉米的重量为 A_i。每次小熊只能选择相邻的两棵玉米合并成一捆，合并的代价为这两棵玉米的重量之和。合并后得到的新玉米重量等于两棵重量之和。  
小熊想把所有玉米最终合并成一捆，请问最小的总合并代价是多少？

输入格式

第一行一个整数 N（1 ≤ N ≤ 300）。  
第二行 N 个整数 A_1, A_2, ..., A_N，表示每棵玉米的重量（1 ≤ A_i ≤ 100）。

输出格式

一行一个整数，表示最小总合并代价。

样例数据

input

4
1 3 5 2

output

22

样例解释

合并顺序：
合并 1 和 3 → 代价 4，新堆 [4,5,2]
合并 4 和 5 → 代价 9，新堆 [9,2]
合并 9 和 2 → 代价 11
总代价 = 4+9+11 = 22

数据范围

1 ≤ N ≤ 300,1 ≤ A_i ≤ 100