일 배정하기 1

N명의 사람과 N개의 일이 있습니다. 각 사람은 정확히 하나의 일을 맡아야 하며, 각 일도 정확히 한 사람에게만 배정되어야 합니다. 모든 사람은 모든 일을 할 수 있습니다.

사람과 일에는 각각 1번부터 N번까지 번호가 붙어 있습니다. D_{ij}를 i번 사람이 j번 일을 할 때 드는 비용이라고 할 때, N개의 일을 모두 배정하는 데 필요한 총비용의 최솟값을 구하세요.

첫째 줄에 사람과 일의 수 N (1 <= N <= 20)이 주어집니다. 다음 N개의 줄에는 비용 행렬 D가 주어집니다. 각 줄에는 N개의 자연수 비용이 있으며, 모든 비용은 10,000 이하입니다.

모든 일을 배정하는 데 필요한 총비용의 최솟값을 출력합니다.