N × N 크기의 정수 행렬이 주어집니다. 이 행렬에서 총 N개의 수를 선택하려고 합니다. 단, 수를 선택할 때는 다음 조건을 만족해야 합니다.

• 각 행(Row)에서 정확히 하나의 수를 선택해야 합니다.
• 각 열(Column)에서 정확히 하나의 수를 선택해야 합니다.

즉, 임의의 두 수가 같은 행에 있거나 같은 열에 있어서는 안 됩니다. 이 조건에 맞게 N개의 수를 선택했을 때, 선택한 수들의 합이 최소가 되도록 하는 프로그램을 작성하시오.

입력

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

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

출력

첫째 줄에 조건에 맞게 선택한 N개 수의 합의 최솟값을 출력한다.

제한 사항

• 1 ≤ N ≤ 10
• 행렬의 각 원소는 1 이상 100 이하의 자연수입니다.

예제 입력 1

3
1 2 5
2 4 3
5 4 3

예제 출력 1

7

예제 입력 2

2
10 20
30 40

예제 출력 2

50