마법사의 배정

N명의 마법사에게 N개의 미션을 하나씩 배정하려고 한다. i번 마법사가 j번 미션을 수행할 때 필요한 마나 비용이 주어진다.

모든 마법사에게 정확히 하나의 미션을 배정하면서, 전체 마나 비용의 합을 최소화하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 10) 둘째 줄부터 N개의 줄에 N개의 정수(마나 비용)가 공백으로 구분되어 주어진다. (각 비용 ≤ 100)

출력

최소 마나 비용의 합을 출력한다.

입출력 예시

입력 1

3
5 8 4
7 6 9
3 5 2

출력 1

13

입력 2

4
10 15 20 25
15 10 25 20
20 25 10 15
25 20 15 10

출력 2

40