题目描述

有一个N×N的方格，部分格子放有正整数，其余格子为0。一个人从左上角出发，每步只能向右或向下，直到右下角。走过一个格子时可以取走其中的数，取走后该格子变成0。

这个人一共从左上角走到右下角两次，两条路线可以重合。求两次取得的数的总和的最大值，每个格子中的数只能贡献一次。

输入格式

第一行一个整数N。接下来若干行，每行三个整数x、y、w，表示第x行第y列放有整数w。未给出的格子为0，同一位置不会重复给出。最后一行是0 0 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≤N≤10，1≤x,y≤N，1≤w≤10000。结束标记0 0 0不受这些限制。