P1775 Merging Stones (Weakened Version)

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.

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

Output a single integer, the minimum cost.

Translated by ChatGPT 5