题目描述

神秘的藏书阁内藏书无数，每一本都代表着智慧。小度是位爱学习的孩子，他的目标是尽可能在规则内获取更多智慧。

藏书阁设有 $N\times N$ 的方格隔间，其中某些方格中放有正整数本书，其他方格中没有书（即为 $0$）。

小度需要从左上角 $(1,1)$ 出发，走到右下角 $(N,N)$，并且一共安排两条路径。每条路径每一步只能向右或向下移动。路径经过某个方格时，可以取得该方格中的书籍；同一个方格中的书籍至多只能被取得一次。

请计算两条路径上取得书籍数量的最大总和。

输入格式

输入第一行为一个整数 $N$，表示方格图大小为 $N\times N$。

接下来的每行有三个整数，前两个表示位置（行、列），第三个数表示该位置上所放的书籍数量。输入以一行 0 0 0 结束。

输出格式

输出一个整数，表示两条路径上取得的最大总和。

样例 #1

输入 #1

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

输出 #1

67

数据范围

• $1\le N\le 9$。
• 每个非零格子中的书籍数量为不超过 $10000$ 的正整数。
• 未被给出的格子中书籍数量为 $0$。