题目描述

设有$\red{ n}$件工作分配给$\red{ n}$个人。将工作$\red{i}$分配给第$\red{j}$个人所需的费用为$\red{c_{ij}}$。

试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。

设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

输入格式

第一行有$\red{1}$个正整数$\red{n}$ ($\red{1≤n≤20}$)。

接下来的n行，每行$\red{n}$个数，第i行表示第$\red{i}$个人各项工作费用。

输出格式

输出最小总费用

样例

输入样例

3
4 2 5
2 3 6
3 4 5

输出样例

9