Hello, Pie!

Pizzeria Pizazz prides itself on delivering pizza to its customers as fast as possible. Unfortunately, only one driver can be hired for delivery. Before delivery, he waits until a certain number of orders arrive (from $1$ to $20$). The driver prefers to choose the fastest route for delivering all orders, even if he has to pass the same place several times, including a pizzeria. At the end of the delivery, the driver must return to the original place, that is, to the pizzeria. You need to write a program that finds such a route.

Input

The first line contains the number of orders $n(1\le n\le 20)$. This is followed by $n+1$ strings, each containing $n+1$ integers. These numbers indicate the travel time between the pizzeria (its number is $0$) and $n$ places where orders are located (they are numbered from $1$ to $n$). The $j$ - th value of the $i$ - th line indicates the time it takes to drive directly from the location $i$ to the location $j$, without visiting any other places along the way. Note that travel between $i$ and $j$ may not be faster directly, but through other locations due to traffic jams and traffic lights. Travel times are not symmetrical. That is, the time it takes to drive directly from $i$ to $j$ does not always coincide with the travel time directly from $j$ to $i$.

Output

Print one number — the shortest time it takes to deliver pizza to all customers and return back to pizzeria.

Examples