拾取物品

题目描述

在 $R$ 行 $C$ 列的棋盘上有 $K$ 个物品。将第 $1 \leq i \leq R$ 行、第 $1 \leq j \leq C$ 列的格子记为 $(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$
$:$
$r_K$ $c_K$ $v_K$

输出格式

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

样例

2 2 3
1 1 3
2 1 4
1 2 5

8

移动方法有以下 $2$ 种:

• 依次经过格子 $(1, 1)$、$(1, 2)$、$(2, 2)$。此时能拾取的物品价值总和为 $3 + 5 = 8$。
• 依次经过格子 $(1, 1)$、$(2, 1)$、$(2, 2)$。此时能拾取的物品价值总和为 $3 + 4 = 7$。

因此,高桥君能拾取的物品价值总和的最大可能值为 $8$。

2 5 5
1 1 3
2 4 20
1 2 1
1 3 4
1 4 2

29

第 $1$ 行有 $4$ 个物品。按如下方式移动并拾取物品是最优的:

• 依次经过格子 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 4)$、$(2, 5)$。其中只不拾取格子 $(1, 2)$ 上的物品,则物品价值总和为 $3 + 4 + 2 + 20 = 29$。

4 5 10
2 5 12
1 5 12
2 3 15
1 2 20
1 1 28
2 4 26
3 2 27
4 5 21
3 5 10
1 3 10

142

数据范围

• $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$
• 输入均为整数