ЗАДАЧА F

Иллюминация

Имя входного файла:light.in
Имя выходного файла:light.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

На международном 2009-ом съезде Дедов Морозов, который проходил в начале декабря этого года в Болгарии под руководством болгарского Деда Мороза Дяди Коледы, рассматривались важнейшие вопросы организации предстоящего новогоднего праздника. Учитывая мировой экономический спад и динамику цен на энергоносители, Деды Морозы рассматривали вопрос подсветки елок, установленных на центральных площадях каждого из N городов Восточной Европы. Было решено не использовать местную электросеть для подсветки, а создать отдельную систему для снабжения новогодних елок электричеством.

В каждом из городов можно построить специальную атомную электростанцию для генерации новогоднего электричества. Учитывая разную экологическую ситуацию в городах, стоимость постройки электростанций различна для разных городов, а именно составляет Ci евротугриков для i-го города. Вместо строительства электростанции, город можно соединить кабелем с другим городом, куда уже было подведено новогоднее электричество. При этом город может снабжаться электростанцией не напрямую, а через несколько других городов. Стоимость прокладки кабеля между i-ым и j-ым городами составляет Ai,j евротугриков.

Определите стоимость системы новогоднего электроснабжения елок, построенной Дедами Морозами, если известно, что они выбрали самый дешевый вариант.

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


В первой строке входного файла содержится единственное целое число N (1 ≤ N ≤ 300) – количество городов. Во второй строке записаны N целых чисел Ci, разделенных пробелами (1 ≤ Ci ≤ 100 000). Следующие (N-1) строк описывают стоимость прокладки кабелей между городами. А именно (i+2)-ая строка содержит (N-i) целых чисел Ai,i+1, Ai,i+2, …, Ai,N (1 ≤ Ai,j ≤ 100 000).

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


В выходной файл выведите единственное целое число – минимально возможную стоимость постройки системы электроснабжения елок, вычисленную в евротугриках.

Пример


light.in light.out Примечание 
4
1 2 3 4
1 5 5
2 5
5
 
8
 Оптимально будет построить электростанции в городах 1 и 4 и проложить кабеля между парами городов 1 и 2, 2 и 3.