\(N \times N\) 크기의 정수 행렬이 주어진다. 이 행렬에서 총 \(N\)개의 수를 선택하려고 한다. 단, 수를 선택할 때는 다음 조건을 만족해야 한다.

• 각 행에서 정확히 하나의 수를 선택해야 한다.
• 각 열에서 정확히 하나의 수를 선택해야 한다.

즉, 임의의 두 수가 같은 행에 있거나 같은 열에 있어서는 안 된다.

조건에 맞게 \(N\)개의 수를 선택했을 때, 선택한 수들의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행렬의 크기 \(N\)이 주어진다.

둘째 줄부터 \(N\)개의 줄에 걸쳐, 행렬의 각 원소를 나타내는 \(N\)개의 정수가 공백을 사이에 두고 주어진다.

출력

조건에 맞게 선택한 \(N\)개 수의 합의 최솟값을 출력한다.

제한 사항

• \(1 \le N \le 15\)
• 행렬의 각 원소는 \(1\) 이상 \(100\) 이하이다.

예제 입력 1

3
1 2 5
2 4 3
5 4 3

예제 출력 1

7

예제 설명 1

1행 2열의 수 2, 2행 1열의 수 2, 3행 3열의 수 3을 선택하면 합은 7이다. 조건을 만족하면서 합을 7보다 작게 만들 수 없으므로 최솟값은 7이다.

예제 입력 2

2
10 20
30 40

예제 출력 2

50