题目背景

Smart 在 Tommy 的追杀下进入一个矿洞，他希望在逃跑的同时开采尽量多的铁矿，使其能够与 Tommy 对抗。

题目描述

Smart 有一个大小为\(n\)的矿洞地图,矿洞入口在左上角，出口在右下角。地图上面标注了铁矿的位置，但是由于 Tommy 紧跟其后，所以 Smart 只能向右或向下走。

但是这样走很明显无法收集足够的铁矿，因此 Smart 做了一个珍珠滞留装置，当他到达终点时，会被传送回起始点，可以再走一次矿洞，挖取更多铁矿(说白了就是能走两次)

但是 Tommy 可以在 Smart 传送到起点时使用 \(tp\) 指令也回到起点，所以 Smart 第二次也只能向右或向下走。

然鹅这个问题过于复杂，他希望会 \(C\texttt{艹}\) 的你帮他解决

格式

输入格式

输入若干行;

第一行一个数字 \(n\) ，代表大小为\(n\)的地图。

接下来输入地图,有若干行(不是 \(n\) 行)。

一行三个数 \(x,y,w\)，代表第 \(x\) 行 \(y\) 列的铁矿含量为\(w\)。

输入以以 \(0\) \(0\) \(0\) 结尾。

输出格式

一个数，表示 Smart 可挖取的最大铁矿数

样例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

限制

\(0 < n < 10\)