【描述】
大家都知道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