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

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

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

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

입력

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

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

출력

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

제한 사항

• 1 ≤ N ≤ 10

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

Line 1: \(N\) (\(1 \le N \le 10\)). Next \(N\) lines: \(N\) integers each (\(1 \le\) value \(\le 100\)).

Print the minimum selectable sum.

riseoj 작성

출처 Online Judge > GoldOJ