Stone Merging

Problem Description

On a playground, $N$ piles of stones are placed in a row. The stones must be merged into a single pile in the given order. In each move you may choose exactly two adjacent piles and merge them into a new pile; the score of that move is the total number of stones in the new pile.

Compute the minimum total score needed to merge the $N$ piles into one pile.

Input Format

The first line contains a positive integer $N$ ($2 \le N \le 100$).

The next $N$ lines each contain a positive integer smaller than $10000$, giving the number of stones in the $i$-th pile ($1 \le i \le N$).

Output Format

A single positive integer: the minimum score.

Sample Input

7
13
7
8
16
21
4
18

Sample Output

239

Limitation

1 s, 1024 KiB for each test case.