1605 - 方格取数

通过次数

7

提交次数

18

Time Limit : 1 秒
Memory Limit : 64 MB

有一个 N*N 的方格图。某些方格中放入了正整数,而其他的方格中则放入了数字0。某人从图的左上角(A点)出发,可以向下行走,也可以向右走,直到到达右下角(B 点)。在走过的路上,他可以取走方格中的数(取走后的方格中数字将变为 0)。

此人从 A 点到 B 点共走两次,试找出 2 条这样的路径,使得取得的数之和为最大。

15654278817037.png

Input

第1行1个整数N,表示N*N的方格图,N≤10。

接下来的每行有3个整数,前两个数表示位置,第3个数为该位置上所放的数。一行单独的3个0表示输入结束,每行的两个数之间有一个空格隔开。

Output

输出一行一个整数,表示2条路径上取得的最大的和。

Examples

Input

8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

Output

67

Source

课课通