Description

There are $N(N \le 300)$ piles of stones in a row, numbered $1, 2, 3, \cdots, N$. Each pile has a mass $m_i\ (m_i \le 1000)$. The goal is to merge these $N$ piles into one pile. Each time, you may only merge two adjacent piles, and the cost of merging is the sum of the masses of these two piles. After merging, the piles that were adjacent to the two merged piles become adjacent to the new pile. Because different merging orders lead to different total costs, find a method that minimizes the total cost, and output the minimum cost.

Input Format

The first line contains an integer $N$. The second line contains $N$ integers $m_i$.

Output Format

Output a single integer, the minimum cost.

4
2 5 3 1

22

Hint

Translated by ChatGPT 5