일 나눠주기

첫 줄에 사람(=일)의 수 n (1 이상 15 이하) 이 주어집니다. 이어서 n개의 줄에 각각 n개의 수가 주어집니다. i번째 줄 j번째 수는 i번 사람이 j번 일을 할 때 드는 비용입니다 (0 이상 1000 이하).

각 사람에게 서로 다른 일 하나씩을 빠짐없이 맡길 때, 비용 합의 최솟값을 출력하세요.

예시

입력

2
1 2
3 4

출력

5