Cheapest Assignment

Statement

There are n workers and n tasks. Giving task j to worker i costs cost[i][j]. Every worker must get exactly one task and every task must go to exactly one worker. Find the minimum possible total cost.

Input

The first line has n. Each of the next n lines has n integers: row i is the costs of worker i.

Output

Print one integer: the minimum total cost.

Constraints

1 <= n <= 12
1 <= cost[i][j] <= 1000000

Example 1

3
9 2 7
6 4 3
5 8 1

9

Worker 1 takes task 2 (cost 2), worker 2 takes task 1 (cost 6), worker 3 takes task 3 (cost 1).

Example 2

2
1 5
5 1

2

Each worker takes the task on the diagonal.