D - Let's go to KSDUPC!
Benihuki
2
s
1024
MB
200
点
問題文
$N$ 人がチームで競技プログラミングのコンテストに参加します。
このコンテストでは問題 $1,$ 問題 $2,$ $...,$ 問題 $N$ の合計 $N$ 問の問題が出されます。
人 $i$ は 問題 $j$ を $A_{i,j}$ 分で解けます。
ただし、$1 $人 $1$ 問しか解けません。
このコンテストでは同時コーディングが禁止されているため、人 $i$ が 問題 $P_i$ を解くとき、チームがすべての問題を解くのにかかる時間は $\sum_{i=1}^{N} A_{i,P_i}$ 分です。
適切に問題分担を行ったとき、すべての問題を解くのにかかる時間の最小値を求めてください。
より厳密には、$(1,2,....,N)$ を並び替えた長さ $N$ の順列を $P$ としたとき、$\sum_{i=1}^{N} A_{i,P_i}$ の最小値を求めてください。
制約
- $2 ≤ N ≤ 17$
- $1 ≤ A_ {i,j} ≤ 10^9$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_{1,1}\ A_{1,2}\ \dots\ A_{1,N}$
$A_{2,1}\ A_{2,2}\ \dots\ A_{2,N}$
$\vdots$
$A_{N,1}\ A_{N,2}\ \dots\ A_{N,N}$
出力
答えを出力せよ。
入力例 1
3
1 2 10
20 30 1
20 40 30
出力例 1
23
$P = (1,3,2)$ のとき、つまり人 $1$ が問題 $1$、人 $2$ が問題 $3$、人 $3$ が問題 $2$ を担当するとき、すべての問題を解くのにかかる時間は $42$ 分です。
$P = (2,3,1)$ のとき、すべての問題を解くのにかかる時間は $23$ 分であり、これが最小値です。
入力例 2
3
100 200 60
20 30 400
20 440 350
出力例 2
110