题目描述

神秘的藏书阁内藏书无数，每一本都珍惜无比代表着智慧，假设智慧与书本的数 量相关，小度是位爱学习的孩子，他的目标是想尽可能的在规则内获取更多智慧， 藏书阁设有 N×N 的方格隔间 (N≤9)，其中的某些方格中有批量藏书（正整数 本），而其他的方格中则有可能没有任何书籍（即放入数字 0）。如下图所示（见 样例）:

现在小度需要从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到 到达右下角的 B 点。在走过的路上，他可以取走方格中的书籍数（取走后的方 格中的书籍数将变为数字 0）。显而易见，更多的书籍数代表着更多智慧，小度 想尽可能的找到合适的路径获得更多的智慧。

假设小度从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之 和（智慧）为最大。

输入格式

输入的第一行为一个整数 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

以样例数据为例：两条路径分别为：21+15=36，13+14+4=31，总和为 67。

说明/提示

数据范围：1≤N≤9。