大家都知道tigertang除了热爱编程之外，他还有一个爱好就是喜欢玩。 某天在河边玩耍的时候，他发现了一种神奇的石子，当把两个石子放在一起的时候，后一个石子会消失，而且会蹦出一定数量的金币，这可乐坏了tigertang，但是他想得到最多的金币，他该怎么做?

有若干组测试数据，对于每组测试数据： 首先一行，一个n（1<=n<=10），表示有n个石子。 接下来n*n的一个矩阵，Aij表示第i个和第j个合并蹦出的金币值(小于10000，注意合并后j会消失)。

输出最多能得到的金币值。

2
0 4
1 0
3
0 20 1
12 0 1
1 10 0

4
22