Оптимальное бинарное дерево поиска

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

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

Стоимостью $cos t$ доступа к элементу $e_{i}$ из $S$ в дереве будем называть значение $cos t (e_{i})$ , равное числу ребер на пути, который соединяет корень с вершиной, содержащей элемент. Имея частоту запросов к элементам из $S$ , $(f (e_{1}), f (e_{2}), ..., f (e_{n}))$ , определим общую стоимость дерева следующим образом:

f (e_{1}) \cdot cos t (e_{1}) + f (e_{2}) \cdot cos t (e_{2}) + ... + f (e_{n}) \cdot cos t (e_{n})

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

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

Состоит из нескольких тестов, каждый из которых расположен в отдельной строке. Первое число в строке $n (1 \leq n \leq 250)$ указывает на размер множества $S$ . Следующие $n$ неотрицательных целых чисел описывают частоты запросов элементов из $S$ : $f (e_{1}), f (e_{2}), ..., f (e_{n}) (0 \leq f (e_{i}) \leq 100)$ .

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

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

Примеры

Ввод #1

Ответ #1

Отправки 1K

Коэффициент принятия 44 %