题目描述

给定一个$n$*$n$的矩阵$A$，其元素$A$$_i$,$j$为整数（$0$ <= $i$ < $n$，$0$ <= $j$ < $n$）。对第$i$行（$0$ <= $i$ < $n$）进行一次SHIFT操作会将该行的整数向右移动一个位置，最右侧的整数会绕回最左侧。

你可以对任意行进行任意次数的SHIFT操作。你的任务是使以下表达式的值最小化：

max$_0$<=$j$< $n${$C$$_j$|$C$$_j$=Σ$0$<=$i$< $n$ $A$$_i$,$_j$}

输入

输入包含多个测试用例。每个测试用例的第一行是一个整数$n$。接下来的$n$行每行包含$n$个整数，表示矩阵$A$。输入以一个单独的$-1$结束。假设$1$ <= $n$ <= $7$且|$A$$_i$,$_j$| < $10$^$4$。

输出

对于每个测试用例，输出一行，包含列和最大值的最小可能值。

样例输入 1

2
4 6
3 7
3
1 2 3
4 5 6
7 8 9
-1

样例输出 1

11
15

来源

2004年上海赛区初赛