eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Привет, Пирог!

Привет, Пирог!

Лимит времени 3 секунды
Лимит использования памяти 512 MiB

Пиццерия Pizazz гордится тем, что она доставляет пиццу своим покупателям как можно быстрее. К несчастью, для доставки может быть нанят только один водитель. Перед развозкой он ждет, пока не поступит определенное количество заказов (от 1 до 20). Водитель предпочитает выбрать для развозки всех заказов самый быстрый путь, даже если придется проезжать несколько раз одно и то же место, включая пиццерию. В конце развозки водитель обязан вернуться в исходное место, то есть в пиццерию. Вам необходимо написать программу, которая выберет такой маршрут.

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

В первой строке находится количество заказов n~(1 \le n \le 20). Далее следует n + 1 строка, каждая из которых содержит n + 1 целое число. Эти числа указывают на время проезда между пиццерией (ее номер 0) и n местами, где находятся заказы (они пронумерованы числами от 1 до n). j-ое значение i-ой строки указывает на время, за которое можно проехать напрямую из места i в место j, не посещая по пути никаких других мест. Заметим, что проезд между i и j может быть быстрее не напрямую, а через другие места из-за пробок на дорогах и присутствия светофоров. Время проезда не симметрично. То есть время, за которое можно напрямую проехать из i в j, не всегда совпадает с временем проезда напрямую из j в i.

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

Выведите одно число — наименьшее время, за которое можно развести пиццу всем заказчикам и вернуться обратно в пиццерию.

Пример

Входные данные #1
3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
Выходные данные #1
8
Источник Летняя Школа 2010, Севастополь, день М.Медведева