문제 102
최소 비용 배정
$N$명의 작업자와 $N$개의 작업이 있다. 작업자 $i$가 작업 $j$를 수행하는 비용은 $A_{i,j}$이다.
모든 작업자에게 서로 다른 작업을 정확히 하나씩 배정할 때, 전체 비용의 합의 최솟값을 구해보자.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 400)$
두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 $N$개의 정수 $A_{i,1}, A_{i,2}, \cdots, A_{i,N}$이 공백으로 구분되어 주어진다. $(-10^9 \le A_{i,j} \le 10^9)$
출력
배정 비용의 합의 최솟값을 출력한다.
예제 입력 1
3 2 1 3 4 0 5 6 7 1
예제 출력 1
3
예제 입력 2
2 5 -4 -1 3
예제 출력 2
-5