11002 - 工作分配（数据增强）

公司分配N项工作给N个员工，每个员工只能被分给1项工作，每个人处理工作的时间不同。求完成所有工作所需的最少时间。

Input

第一行输入整数N,代表N个员工，员工编号从1到N（10<=N<=20）

接下来输入一个N*N的二维矩阵task[N][N],其中task[i][j]（0<=task[i][j]<=1000）代表第i项工作由j号员工完成所需的时间。

Output

输出一个整数，代表完成所有工作所需的最少时间之和。

Examples

Input

6
10 11 12 11 9 11
11 9 10 13 11 12
12 10 11 10 13 9
9 14 9 10 10 11
10 10 9 11 12 11
10 7 10 10 10 8

Output

54
Time Limit 1000 毫秒
Memory Limit 256 MB
Stats
上一题 下一题