Рассмотрим множество S = {e1, e2, ..., en}, состоящее из n различных элементов таких, что e1 < e2 < ... < en. Рассмотрим бинарное дерево поиска, состоящее из элементов S. Чем чаще производится запрос к элементу, тем ближе он должен располагаться к корню.

Стоимостью cost доступа к элементу ei из S в дереве будем называть значение cost(ei), равное числу ребер на пути, который соединяет корень с вершиной, содержащей элемент. Имея частоту запросов к элементам из S, (f(e1), f(e2), ..., f(en)), определим общую стоимость дерева следующим образом:

f(e1) · cost(e1) + f(e2) · cost(e2) + ... + f(en) · cost(en)

Дерево, имеющее наименьшую стоимость, считается наилучшим для поиска элементов из S. Именно поэтому оно называется Оптимальным Бинарным Деревом Поиска.

Входные данные

Состоит из нескольких тестов, каждый из которых расположен в отдельной строке. Первое число в строке n (1 ≤ n ≤ 250) указывает на размер множества S. Следующие n неотрицательных целых чисел описывают частоты запросов элементов из S: f(e1), f(e2), ..., f(en). Известно, что 0 ≤ f(ei) ≤ 100.

Выходные данные

Для каждого теста в отдельной строке вывести стоимость Оптимального Бинарного Дерева Поиска.