Assignment problem

One of the classical problems of combinatorial optimization is the "assignment problem". It is formulated as follows.

There are $n$ workers, numbered from $1$ to $n$, and $n$ jobs, numbered from $1$ to $n$. If the $i$-th worker is assigned to the $j$-th job, he gets salary $c_{ij}$ money. Find such assignment of workers to the jobs (each worker can perform only one job, each job is performed by only one worker) so that the total worker's salary is minimized (the corresponding sum is called the cost of assignment).

Write the program to solve the assignment problem.

Input

First line contains one integer $n(1\le n\le 10)$.

Each of the next $n$ lines contains $n$ integers. The $j$-th number of the $(i+1)$-th line equals to $c_{ij}(1\le c_{ij}\le 1000)$.

Output

Print the minimum possible cost of assignment.

Examples