#AC1950. NOIP 2000 方格取数

NOIP 2000 方格取数

题目描述

输入格式

输入的第一行为一个整数N(表示N*N的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的0表示输入结束。
 

输出格式

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

样例

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
67

来源:提高组