选择小组，然后选择自己班级，开始练习！
Description
星星同学在参加完校园文化艺术节后回去的路上发现了一个神奇的地图，地图有 n×m 个方格组成，地图上放置着 k 个物品，第 i 个物品在格子（n_i,m_i），价值为 v_i。星星从格子（1，1）出发，向格子（n,m）移动。星星在格子（i , j）时，可以走到格子（i+1 , j）或格子（i , j+1）。星星可以拾取路过的格子的物品（包括起点和终点格子），但是同一行的物品最多只能拾取 3 个。
请你编写程序求星星可以拾取物品总价值的最大值。
【数据范围】
1 ≤ n,m ≤ 3000 ,
1 ≤ k ≤ 2×10^5
1 ≤ v_i ≤ 10^9
Input
从文件 plat.in 输入。
输入一行 3 个整数，n,m 和 k，表示地图有 n 行和 m 列，地图上放置着 k件物品。
接下来输入 k 行，每行 3 个整数 n_i，m_i，v_i，表示第 i 个物品所在的格子的横纵坐标和物品价值。
Output
输出到文件 plat.out。
输出一行一个整数，表示星星可以拾取的物品总价值的最大值。
Examples
Input
2 2 3 1 1 3 2 1 4 1 2 5
Output
8
Input
2 5 5 1 1 3 2 4 20 1 2 1 1 3 4 1 4 2
Output
29
Input
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
Output
142
Hint
【样例 1 解释】
有一个 2 行 2 列的地图，地图上有 3 件物品。接下来 3 行，第一行表示第一个物品在格子（1,1）上，价值为 3；第二行表示第二个物品在格子（2,1）上价值为 4；第三行表示第三个物品在格子（1,2）上价值为 5。星星拾取第一个物品
后，因为只能向下或者向右走，所以接下来选择第三个物品时总价值最大，最大值为 8。
Source
2024洛阳市竞赛