Problems
Assignment problem
Assignment problem
One of the classical problems of combinatorial optimization is the "\textit{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 \textit{cost of assignment}).
Write the program to solve the assignment problem.
\InputFile
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)$.
\OutputFile
Print the minimum possible cost of assignment.
Input example #2
2 1 2 3 4
Output example #2
5
Input example #1
3 5 2 3 4 2 1 3 7 6
Output example #1
6