逃往芜湖~起飞

不会吧不会吧，不会真有人觉得卢宝逃亡失败了吧？经过了一路的逃亡，卢宝决定先去芜湖圣地躲避一下风头，当卢宝到达芜湖圣地的时候，发现芜湖圣地的前方出现了一块奇异的稻田，卢宝心想，难道这就是麦田怪圈吗？一片看去，麦圈是一个 n*n 的方田，每个单元格内都显示着一个一个奇怪的数字，不懂魔法的人走进去后便会迷失在怪圈之中。老爹曾经说过：要用魔法打败魔法。再三考虑，卢宝决定学习一手魔法，以便自己逃往芜湖圣地

经过一段时间的学习，卢宝终于掌握了魔法的精髓所在，面对 n*n 的麦田，卢宝也必须施展魔法，建立一个 n*n 的魔法阵，卢宝施展了魔法阵大喊道：怪圈，我要进来了！

因为卢宝是魔法初学者，魔法值较低，所建立的魔法阵被魔法值所约束着，需要满足下面的几个约束条件

1. 魔法阵 X_ij 的每个单元只能是 1 或 0

2. X₁₂+X₁₃+...X_1n=1

3. X_1n+X_2n+...X_n-1n=1

4. 对于每一个i (1<i<n)，必须满足∑X_ki (1<=k<=n)=∑X_ij (1<=j<=n).

卢宝为了使得自己的逃亡踪迹不被发现，就要使得其魔法阵与麦田怪圈反应时的魔法反应值最小

及 ∑Cij*Xij 的最小值 （C_ij 为麦田怪圈，X_ij 为卢宝魔法阵）

多组输入（最多35组）

对于每个组数据输入第一行一个 n （1<n<=300）

接下来给出 n*n 的麦田怪圈，每个单元格内包含一个奇怪的数字 C_ij （0<=C_ij<=100000)

对于每组样例，输出卢宝所能建立的各种魔法阵施展时的最小魔法反应值

魔法反应值：∑C_ij*X_ij 的最小值

4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2

3

对于样例而言，如果 n = 4, 卢宝可以建立满足以下条件的魔法阵

X12+X13+X14=1 

X14+X24+X34=1

X12+X22+X32+X42=X21+X22+X23+X24

X13+X23+X33+X43=X31+X32+X33+X34


当卢宝的魔法阵是 X12 =X24 =1，其他的单元格元素都是0时，魔法阵与麦田怪圈的魔法反应值最小