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

Даны $n$ различных элементов в возрастающем порядке и частоты обращений к ним $f_1, \ldots, f_n$. Стоимость доступа к элементу - количество рёбер на пути от корня до него. Общая стоимость дерева - сумма $f_i \cdot \mathrm{cost}(e_i)$.

Найдите наименьшую возможную стоимость.

Обратите внимание: дерево должно быть деревом поиска, то есть порядок элементов задан жёстко. Просто положить самый частый элемент в корень нельзя - от этого зависит, какие элементы попадут налево, а какие направо.

Каждая строка - отдельный тест: сначала число $n$ ($1 \le n \le 250$), затем $n$ чисел $f(e_i)$ ($0 \le f(e_i) \le 100$).

Сумма $n$ по всем тестам не превосходит 5000. Читать надо до конца файла.

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