Problem Description

There are $n$ cities numbered from $1$ to $n$. For every two distinct cities $i,j$, there is a directed road from $i$ to $j$ with cost $c_{i,j}$.

A travelling salesman starts in city $1$. He must visit every city exactly once and finally return to city $1$.

Note that $c_{i,j}$ and $c_{j,i}$ are not necessarily equal.

Find the minimum total cost of such a trip.

Input Format

The first line contains one integer $n$, the number of cities.

The following $n$ lines each contain $n$ integers. The $j$-th integer on the $i$-th line is $c_{i,j}$, the cost of the directed road from city $i$ to city $j$.

It is guaranteed that $c_{i,i}=0$, and $1\le c_{i,j}\le10^9$ for $i\ne j$.

Output Format

Print one integer, the minimum total cost.

Samples

Sample 1

Input:

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

Output:

35

Constraints