Minimal price P20023

You have n tasks to do, and n workers that can do them. For each task 1 ≤ i ≤ n and each worker 1 ≤ j ≤ n, p[i][j] is the price that the worker i does the task j.

Write a program that computes the minimal price of assigning exactly one different task to each worker.

Input

Input consists of a natural 1 ≤ n ≤ 10, followed by p, the matrix n × n of prices (n lines with n natural numbers between 1 and 1000).

Output

Your program must print the minimal price of assigning exactly one different task to each worker.

Observation

There are algorithms of polynomial cost to solve this problem, but are difficult to program. Implement a backtracking.