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.

Public test cases

**Input**

3 5 2 1 2 1 3 1 3 7

**Output**

3

**Input**

4 2 5 7 9 2 2 2 2 2 1 8 3 2 9 9 8

**Output**

12

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++