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: $$ f(e_1) \cdot cost(e_1) + f(e_2) \cdot cost(e_2) + ... + f(e_n) \cdot cost(e_n) $$ 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. \InputFile 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)$. \OutputFile For each test case print a line with the total cost of the Optimal Binary Search Tree.