题目描述

设有 $n$ 件工作分配给 $n$ 个人，将工作 $i$ 分配给第 $j$ 个人费用为 $C_{ij}$，为每个人分配一件不同的工作，对于给定的工作费用，计算最佳工作分配方案，使得总费用达到最小。

输入输出格式

输入

第一行有 $1$ 个正整数($1<=n<=20$)。接下来的 $n$ 行，每行 $n$ 个数，第 $i$ 行表示第 $i$ 个人从事各项工作的费用。

输出

共一行，即最小总费用。

样例

输入1

3
4 2 5
2 3 6
3 4 5

输出1

9

时间及空间限制

1s, 256MB.