Description

There are N piles of stones arranged in a row on a playground. The task is to merge the stones into a single pile in an orderly manner. The rule is that only two adjacent piles can be merged at a time, and the number of stones in the new pile is recorded as the score for that merge. Calculate the minimum total score required to merge the N piles of stones into one.

Input Format

The first line contains a positive integer N (2 ≤ N ≤ 100).
The following N lines each contain a positive integer less than 10000, representing the number of stones in the i-th pile (1 ≤ i ≤ N).

Output Format

A positive integer, the minimum total score.

7
13
7
8
16
21
4
18

239