Рассмотрим множество $S = \{e_1, e_2, ..., e_n\}$, состоящее из $n$ различных элементов таких, что $e_1 < e_2 < ... < e_n$. Рассмотрим бинарное дерево поиска, состоящее из элементов $S$. Чем чаще производится запрос к элементу, тем ближе он должен располагаться к корню. Стоимостью $cost$ доступа к элементу $e_i$ из $S$ в дереве будем называть значение $cost(e_i)$, равное числу ребер на пути, который соединяет корень с вершиной, содержащей элемент. Имея частоту запросов к элементам из $S$, $(f(e_1), f(e_2), ..., f(e_n))$, определим общую стоимость дерева следующим образом: $$ f(e_1) \cdot cost(e_1) + f(e_2) \cdot cost(e_2) + ... + f(e_n) \cdot cost(e_n) $$ Дерево, имеющее наименьшую стоимость, считается наилучшим для поиска элементов из $S$. Именно поэтому оно называется Оптимальным Бинарным Деревом Поиска. \InputFile Состоит из нескольких тестов, каждый из которых расположен в отдельной строке. Первое число в строке $n~(1 \le n \le 250)$ указывает на размер множества $S$. Следующие $n$ неотрицательных целых чисел описывают частоты запросов элементов из $S$: $f(e_1), f(e_2), ..., f(e_n)~(0 \le f(e_i) \le 100)$. \OutputFile Для каждого теста в отдельной строке вывести стоимость Оптимального Бинарного Дерева Поиска.