# Dynamic programming O(n^3)

# Optimal Binary Search Tree

Given a set **S** = {`e`

, _{1}`e`

, ..., _{2}`e`

} of _{n}**n** distinct elements such that `e`

< _{1}`e`

< ... < _{2}`e`

and considering a binary search tree of the elements of _{n}**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`

of _{i}**S** in a tree **cost**(`e`

) 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 _{i}**S**, (**f**(`e`

), _{1}**f**(`e`

), ..., _{2}**f**(`e`

)), we say that the total cost of a tree is the following summation:_{n}

**f**(`e`

) · _{1}**cost**(`e`

) + _{1}**f**(`e`

) · _{2}**cost**(`e`

) + ... + _{2}**f**(`e`

) · _{n}**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.

#### Input

Contains several instances, one per line. Each line will start with a number **n** (**1** ≤ **n** ≤ **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`

). It is known that _{n}**0** ≤ **f**(`e`

) ≤ _{i}**100**.

#### Output

For each input instance you must print a line with the total cost of the Optimal Binary Search Tree.

1 5 3 3 1 7 7 4 10 6 2 3 5 7 6 1 3 5 10 20 30

0 5 49 63