Розглянемо множину $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 Для кожного тесту в окремому рядку вивести вартість Оптимального Бінарного Дерева Пошуку.