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

Пиццерия 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$.

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

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

Примеры