题目描述

在 $N\times N$ 方格中有一些非负整数。从左上角到右下角走两次，每次只能向下或向右。经过格子时可以取走数字，取走后该格数字变成0。求两次一共能取走的最大总和。

输入格式

第一行 $N$。随后每行三个整数 $x,y,v$ 表示格子中的正整数，每个位置至多描述一次；未描述的位置为0。0 0 0 结束。

输出格式

输出最大的数字总和。

样例

2
1 1 1
1 2 2
2 1 3
2 2 4
0 0 0

10

数据范围

$1\le N\le10$，$1\le x,y\le N$，$1\le v\le10000$。