Stone Merging

There are N piles of stones arranged in a row, numbered from 1 to \(N\) (with \(N \le 300\)). Each pile has a weight \(m_i\) (with \(m_i \le 1000\)). The goal is to merge these \(N\) piles into one pile.

You can only merge two adjacent piles at a time. The cost to merge two adjacent piles is equal to the sum of their weights. After a merge, the new pile takes the position of the merged piles, and its weight is the sum of the weights of those piles. Note that the total cost depends on the order in which you merge the piles.

Your task is to determine a strategy such that the total cost of merging is minimized, and output this minimum cost.

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 300\)).

The second line contains \(N\) positive integers \(m_1, m_2, \ldots, m_N\) (each \(m_i \le 1000\)), separated by spaces, representing the weights of the stone piles.

outputFormat

Output a single integer representing the minimum total cost needed to merge all the piles into one.

sample

1
100

0