AT_abc175_e [ABC175E] Picking Goods

在一个有 $R$ 行 $C$ 列的网格中，放置了 $K$ 个物品。用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子，第 $i$ 个物品位于格子 $(r_i, c_i)$，其价值为 $v_i$。 高桥君从格子 $(1, 1)$ 出发，移动到终点格子 $(R, C)$。当高桥君处于格子 $(i, j)$ 时，可以移动到（如果存在的话）格子 $(i+1, j)$ 或格子 $(i, j+1)$。 高桥君可以拾取经过的格子（包括起点和终点）上的物品。但在同一行中，最多只能拾取 $3$ 个物品。如果经过的格子上有物品，也可以选择不拾取。 请你求出高桥君能够拾取的物品价值之和的最大可能值。

输入通过标准输入给出，格式如下： > $R$ $C$ $K$ > $r_1$ $c_1$ $v_1$ > $r_2$ $c_2$ $v_2$ > $\vdots$ > $r_K$ $c_K$ $v_K$

输出高桥君能够拾取的物品价值之和的最大可能值。

## 限制条件 - $1 \leq R, C \leq 3000$ - $1 \leq K \leq \min(2 \times 10^5, R \times C)$ - $1 \leq r_i \leq R$ - $1 \leq c_i \leq C$ - $(r_i, c_i) \neq (r_j, c_j)\ (i \neq j)$ - $1 \leq v_i \leq 10^9$ - 所有输入均为整数 ## 样例解释 1 有以下两种移动方式： - 按顺序经过格子 $(1, 1)$、$(1, 2)$、$(2, 2)$，此时可拾取的物品价值之和为 $3 + 5 = 8$。 - 按顺序经过格子 $(1, 1)$、$(2, 1)$、$(2, 2)$，此时可拾取的物品价值之和为 $3 + 4 = 7$。 因此，高桥君能够拾取的物品价值之和的最大可能值为 $8$。 ## 样例解释 2 第 $1$ 行有 $4$ 个物品。最优的拾取方式如下： - 按顺序经过格子 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 4)$、$(2, 5)$，其中只不拾取格子 $(1, 2)$ 上的物品，物品价值之和为 $3 + 4 + 2 + 20 = 29$。 由 ChatGPT 4.1 翻译