Optimal Binary Search Tree

Given a set $S=\{e_1,e_2,...,e_n\}$ of $n$ distinct elements such that $e_1<e_2<...<e_n$ and considering a binary search tree of the elements of $S$, it is desired that higher the query frequency of an element, closer will it be to the root.

The $cost$ of accessing an element $e_i$ of $S$ in a tree $cost(e_i)$ is equal to the number of edges in the path that connects the root with the node that contains the element. Given the query frequencies of the elements of $S$, $(f(e_1),f(e_2),...,f(e_n))$, we say that the total cost of a tree is the following summation:

In this manner, the tree with the lowest total cost is the one with the best representation for searching elements of $S$. Because of this, it is called the Optimal Binary Search Tree.

Input

Contains several instances, one per line. Each line will start with a number $n(1\le n\le 250)$, indicating the size of $S$. Following $n$, in the same line, there will be $n$ non-negative integers representing the query frequencies of the elements of $S$: $f(e_1),f(e_2),...,f(e_n)(0\le f(e_i)\le 100)$.

Output

For each test case print a line with the total cost of the Optimal Binary Search Tree.

Examples