작업 배정 최적화

N명의 작업자와 N개의 작업이 있다. i번 작업자가 j번 작업을 수행하는 데 드는 비용은 C[i][j]이다.

각 작업자는 정확히 하나의 작업을 수행해야 하고, 각 작업은 정확히 한 명의 작업자가 수행해야 한다. 전체 비용의 합을 최소화하는 배정을 구하고 그 최솟값을 출력하시오.

입력

첫째 줄에 N이 주어진다. (1 <= N <= 16)
둘째 줄부터 N개의 줄에 걸쳐 N x N 비용 행렬이 주어진다. 각 줄은 N개의 정수가 공백으로 구분되어 있다. (1 <= C[i][j] <= 100)

출력

최소 총 비용을 출력한다.

입출력 예시

입력 1

3
10 5 13
3 7 11
8 6 2

출력 1

10

입력 2

2
1 3
2 1

출력 2

2