You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在云南保山的优质小绿豆种植基地，有一个 $N \times N$ 的网格状豆田，某些网格中种有保山小绿豆（用正整数表示克数），其余网格没有绿豆。 阿普（一位豆农）从左上角的 A 点（田边仓库）出发，先走到右下角的 B 点（晒豆场），然后从 B 点返回到 A 点。

• 去程：只能向下或向右移动；
• 返程：只能向上或向左移动。

阿普会收获经过的网格中的绿豆。一旦某个网格的绿豆被收走，该处的克数变为 0（同一网格即使两次经过，也只能收获一次）。 问：阿普最多能收获多少斤保山小绿豆？

输入格式

第一行一个整数 $N$，表示豆田网格大小为 $N \times N$。 接下来若干行，每行三个整数 $x, y, w$，表示网格 $(x, y)$ 处的绿豆克数为 $w$。 输入以 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解释

一种可行的方案如下：

路径经过的总和为$13+14+4+15+21=67$。

2
1 2 5
0 0 0

5

样例2解释

网格大小为$2 \times 2$。只有格子 $(1,2)$ 有 5 克绿豆。

总收获为 5 克。

3
1 2 1
2 1 1
2 3 1
3 2 1
2 2 100
0 0 0

104

样例3解释

一种可行的方案如下：

说明

• 网格坐标从 1 开始编号，左上角 A 点为 (1,1)（仓库），右下角 B 点为 (N,N)（晒豆场）。
• 去程只能向下或向右，返程只能向上或向左，同一网格的绿豆只能被收获一次。

数据规模与约定

对于所有测试数据，保证：$1 < N ≤ 2\times 10^2$,$1\le x, y \le N$,$1\le w \le 10^5$