题目描述

有一个 $N \times N$ 的宝藏网格（$N \le 9$），部分格子中放置了宝石（正整数表示宝石价值），其余格子为空（价值为 $0$）。

探险家从左上角出发，每次只能向右或向下走一格，到达右下角后原路返回起点（返回时也只能向右或向下走）。经过一个格子时可以取走其中的宝石，取走后该格子变为 $0$。

请找出两条这样的路径（去程和回程），使得取走的宝石总价值最大。

输入格式

第一行一个整数 $N$，表示网格大小。

接下来若干行，每行三个整数 $x, y, v$，表示第 $x$ 行第 $y$ 列有宝石价值为 $v$。

输入以一行单独的 0 结束。

输出格式

一行一个整数，表示两条路径取走的宝石总价值的最大值。

样例

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

提示

对于全部测试数据，$1 \le N \le 9$，$1 \le x, y \le N$，$1 \le v \le 30$。