405386: GYM101931 I Торговый день - 2

I. Торговый день - 2ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

На рынке Японии вы уже побывали, а теперь зайдем в кондитерскую. Торт представляет из себя правильный $$$N$$$-угольник. Каждое утро кондитер разрезает свежеиспеченный торт на треугольные кусочки, делая разрезы по диагоналям $$$N$$$-угольника. Для каждого такого разреза известен размер усилия, которое нужно приложить кондитеру, чтобы совершить его.

Помогите кондитеру максимально выгодно разрезать торт, минимизировав прилагаемые усилия.

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

На вход подается число $$$4\leq N \leq 500$$$ - количество вершин $$$N$$$-угольника.

Далее идут $$$N$$$ строк, содержащих по $$$N$$$ целых чисел $$$a_{i,j}$$$ ($$$0\leq a_{i,j} \leq 1000$$$) $$$i,j=1,\ldots,N$$$, которые задают усилия, необходимые для совершения диагонального разреза из вершины $$$i$$$ в вершину $$$j$$$. Гарантируется, что $$$a_{i,i}=a_{i,i+1}=0$$$, $$$i=1,\ldots,N$$$.

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

Единственное число, которое задает минимальное количество усилий, необходимых кондитеру.

ПримерыВходные данные

4
0 0 2 0
0 0 0 5
2 0 0 0
0 5 0 0

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

2

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

5
0 0 2 3 0
0 0 0 5 1
2 0 0 0 7
3 5 0 0 0
0 1 7 0 0

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

5