Задачи
Привет, Пирог!
Привет, Пирог!
\includegraphics{https://static.e-olymp.com/content/ed/ed7ef2c44f3b7c30075b661a9c553afe6f74ef77.gif}
Пиццерия Pizazz гордится тем, что она доставляет пиццу своим покупателям как можно быстрее. К несчастью, для доставки может быть нанят только один водитель. Перед развозкой он ждет, пока не поступит определенное количество заказов (от $1$ до $20$). Водитель предпочитает выбрать для развозки всех заказов самый быстрый путь, даже если придется проезжать несколько раз одно и то же место, включая пиццерию. В конце развозки водитель обязан вернуться в исходное место, то есть в пиццерию. Вам необходимо написать программу, которая выберет такой маршрут.
\InputFile
В первой строке находится количество заказов $n~(1 \le n \le 20)$. Далее следует $n + 1$ строка, каждая из которых содержит $n + 1$ целое число. Эти числа указывают на время проезда между пиццерией (ее номер $0$) и $n$ местами, где находятся заказы (они пронумерованы числами от $1$ до $n$). $j$-ое значение $i$-ой строки указывает на время, за которое можно проехать напрямую из места $i$ в место $j$, не посещая по пути никаких других мест. Заметим, что проезд между $i$ и $j$ может быть быстрее не напрямую, а через другие места из-за пробок на дорогах и присутствия светофоров. Время проезда не симметрично. То есть время, за которое можно напрямую проехать из $i$ в $j$, не всегда совпадает с временем проезда напрямую из $j$ в $i$.
\OutputFile
Выведите одно число --- наименьшее время, за которое можно развести пиццу всем заказчикам и вернуться обратно в пиццерию.
Входные данные #1
3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0
Выходные данные #1
8