Balanced Task Assignment

Balanced Task Assignment

There are n workers and n tasks. Assigning worker i to task j costs ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​​​‌​‌‌​​‌​​​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​​‌​cost[i][j]. Each worker must be assigned exactly one distinct task (a perfect matching). Find the minimum possible total cost.

Input

Line 1: integer n (1 ≤ n ≤ 18) Next n lines: n integers each — row i is cost[i][0..n-1] ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​​​‌​‌‌​​‌​​​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​​‌​(1 ≤ cost[i][j] ≤ 1000)

Output

A single integer: the minimum total assignment cost.

Example

Input:

3
9 2 7
6 4 3
5 8 1

Output:

9

Explanation: assign worker 1 to task 2 (cost 2), worker 2 to task 1 (cost 6), ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​​​‌​‌‌​​‌​​​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​​‌​worker 3 to task 3 (cost 1) — total 2 + 6 + 1 = 9.

Constraints

• 1 ≤ n ≤ 18 ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​‌‌​​‌​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​​​‌​‌‌​​‌​​​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​​​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​​‌​

2
1 2
2 1

2

3
9 2 7
6 4 3
5 8 1

9