时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需(1≤i≤n)要机器j(1≤j≤2)的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和：。要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

tji 机器1 机器2
作业1 2 1
作业2 3 1
作业3 2 3
例如，对于这张表格所示的情况，3个作业有3!=6种可能调度方案，很显然最坏复杂度即为O(n!)。如果按照2,3,1的顺序,则作业2的完成时间为4，作业3的完成时间为8，作业1的完成时间为9，完成时间和为21。最优的作业调度顺序为最佳调度方案是1,3,2，其完成时间和为18。

【输入格式】

　　第一行是正整数 \(m\)。
　　接下来的 \(m\) 行，每行包含m个正整数，其中第 \(i+1\) 行第 \(j\) 个数的正整数表示 \(w[i][j]\)。

【输出格式】

　　输出一个整数，表示最少的加工费。

【输入输出样例1】

　Input

3
3 2 4
5 6 3
5 1 2

　Output

7

【数据限制】

　　\(2≤m≤20\)
　　\(1≤w[i][j]≤100000\)

【来源】

　Mr.he