问题陈述

在一个 $R$ 行 $C$ 列的方格网格上放置了 $K$ 个物品。设 $(i, j)$ 表示第 $i$ 行（$1 \leq i \leq R$）和第 $j$ 列（$1 \leq j \leq C$）的方格。第 $i$ 个物品位于 $(r_i, c_i)$，其价值为 $v_i$。

高桥将从起点 $(1, 1)$ 开始，到达目标点 $(R, C)$。当他在 $(i, j)$ 时，可以移动到 $(i + 1, j)$ 或 $(i, j + 1)$（但不能移动到不存在的方格）。

他可以拾取访问过的方格上的物品，包括起点和目标点，但每行最多只能拾取三个物品。可以忽略掉访问过的方格上的物品。

找到他可以拾取的物品价值的最大可能总和。

约束条件

• $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$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入中给出：

$R$ $C$ $K$ $r_1$ $c_1$ $v_1$ $r_2$ $c_2$ $v_2$ $:$ $r_K$ $c_K$ $v_K$

输出

打印高桥可以拾取的物品价值的最大可能总和。

示例输入 1

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

示例输出 1

8

他有两种方法可以到达目标点：

• 按顺序访问 $(1, 1)$、$(1, 2)$ 和 $(2, 2)$。在这种情况下，他可以拾取的物品总价值为 $3 + 5 = 8$。
• 按顺序访问 $(1, 1)$、$(2, 1)$ 和 $(2, 2)$。在这种情况下，他可以拾取的物品总价值为 $3 + 4 = 7$。

因此，他可以拾取的物品价值的最大可能总和为 $8$。

示例输入 2

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

示例输出 2

29

我们在第一行有四个物品。最优的选择如下：

• 按顺序访问 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(1, 4)$、$(2, 4)$ 和 $(2, 5)$，并拾取除 $(1, 2)$ 外的所有物品。然后，他拾取的物品的总价值将为 $3 + 4 + 2 + 20 = 29$。

示例输入 3

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

示例输出 3

142