## Problem Description

There are n blocks of stones in a line laying on the ground. Now you are to merge these blocks of stones together with the restriction that you can only merge the neighbouring blocks each time. The score you get for each merging is the number of stones the new blocks has.

Before **each** merging, you are allowed to swap any neighbouring blocks **for any times**. You are to calculate the minimal score you will get during the whole process.

## Input

There are multiple test cases. For each case, the first line contains a integer n(n<=10000), representing the number of blocks. The second line contains n integers, representing number of stones in each blocks.

## Output

For each case, output one line containing a single integer, representing the minimal score. The results are within 32bit integers.

## Sample Input

3
2 5 1

## Sample Output

11

## Source

chenyan