#P1884. 合并游戏

合并游戏

    大家都知道Yougth除了热爱编程之外,他还有一个爱好就是喜欢玩。

    某天在河边玩耍的时候,他发现了一种神奇的石子,当把两个石子放在一起的时候,后一个石子会消失,而且会蹦出一定数量的金币,这可乐坏了Yougth,但是他想得到最多的金币,他该怎么做?

Input

首先一行,一个n(1<=n<=10),表示有n个石子。
接下来n*n的一个矩阵,Aij表示第i个和第j个合并蹦出的金币值(小于10000,注意合并后j会消失)。

Output

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

Sample Input

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

Sample Output

4
22

HINT

Source