Привіт, Пиріг!

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

Вихідні дані

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

Приклади