{"trustable":false,"sections":[{"title":"Description","value":{"format":"MD","content":"Given a set \u003ci\u003eS\u003d(e\u003csub\u003e1\u003c/sub\u003e, e\u003csub\u003e2\u003c/sub\u003e, ... , e\u003csub\u003en\u003c/sub\u003e)\u003c/i\u003e of *n* distinct elements such that \u003ci\u003ee\u003csub\u003e1\u003c/sub\u003e \u003c e\u003csub\u003e2\u003c/sub\u003e \u003c ... \u003c e\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e and considering a binary search tree (see the previous problem) of the elements of *S*, it is desired that higher the query frequency of an element, closer will it be to the root.\n\nThe cost of accessing an element \u003ci\u003ee\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e of *S* in a tree (\u003ci\u003ecost(e\u003csub\u003ei\u003c/sub\u003e)\u003c/i\u003e) 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*, \u003ci\u003e(f(e\u003csub\u003e1\u003c/sub\u003e), f(e\u003csub\u003e2\u003c/sub\u003e), ... , f(e\u003csub\u003en\u003c/sub\u003e))\u003c/i\u003e, we say that the total cost of a tree is the following summation:\n\n\u003ccenter\u003e\u003ci\u003ef(e\u003csub\u003e1\u003c/sub\u003e)\\*cost(e\u003csub\u003e1\u003c/sub\u003e) +f(e\u003csub\u003e2\u003c/sub\u003e)\\*cost(e\u003csub\u003e2\u003c/sub\u003e) +...+f(e\u003csub\u003en\u003c/sub\u003e)\\*cost(e\u003csub\u003en\u003c/sub\u003e)\u003c/i\u003e\u003c/center\u003e\n\nIn 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."}},{"title":"Input","value":{"format":"MD","content":"The input will contain several instances, one per line.\n\nEach line will start with a number \u003ci\u003e1≤n≤250\u003c/i\u003e, 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 \u003ci\u003eS: f(e\u003csub\u003e1\u003c/sub\u003e), f(e\u003csub\u003e2\u003c/sub\u003e), ... , f(e\u003csub\u003en\u003c/sub\u003e)\u003c/i\u003e, \u003ci\u003e0≤f(e\u003csub\u003ei\u003c/sub\u003e)≤100\u003c/i\u003e. Input is terminated by end of file."}},{"title":"Output","value":{"format":"MD","content":"For each instance of the input, you must print a line in the output with the total cost of the Optimal Binary Search Tree."}},{"title":"Sample Input","value":{"format":"MD","content":"1 5\n3 10 10 10\n3 5 10 20"}},{"title":"Sample Output","value":{"format":"MD","content":"0\n20\n20"}}]}