006 - Simple Grid Problem

問題

縦$ \ H \ $マス、横$ \ W \ $マスの$ \ H \times W \ $マスからなるマス目を持っています。
上から$ \ y \ (1 \leq y \leq H) \ $行目、左から$ \ x \ (1 \leq \ x \leq W) \ $列目のマスをマス$ \ (y,x) \ $と表します。

このマス目では、現在いるマスがマス$ \ (y,x) \ $であるとき、マス$ \ (y,x) \ $からはマス$ \ (y+1,x) \ $またはマス$ \ (y,x + 1) \ $へと移動することができます。また、マスの中には得点が得られるマスが$ \ N \ $カ所存在し、マス$ \ (Y_i,X_i) \ (1 \leq i \leq N) \ $にたどり着くことで得点$ \ P_i \ $点を獲得することができます。

マス$ \ (1,1) \ $からマス$ \ (H,W) \ $へと移動するとき、獲得できる得点の総和の最大値を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$H \ W \ N$
$Y_1 \ X_1 \ P_1$
$Y_2 \ X_2 \ P_2$
$\vdots$
$Y_N \ X_N \ P_N$

出力

得点の総和の最大値を出力せよ。出力の末尾には改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq H,W \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Y_i \leq H$
• $1 \leq X_i \leq W$
• $\{Y_i,X_i\} \neq \{Y_j,X_j\} \ (i \neq j)$
• $1 \leq P_i \leq 10^9$
• 入力は全て整数

入出力例

入力例1

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

出力例1

30

例として、$(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3) \to (3,4) \ $と移動することで得点は$ \ 10 + 20 = 30 \ $となります。

---

入力例2

1 1 1
1 1 100

出力例2

100

全く移動を行わずに$ \ 100 \ $点を得ることができます。