P3431 [POI 2005] AUT-The Bus

字节市的街道形成了一个规则的棋盘状网络——它们要么是南北方向，要么是东西方向。我们称它们为 NS 街道和 WE 街道。此外，每条街道都贯穿整个城市。每条 NS 街道与每条 WE 街道相交，反之亦然。NS 街道从最西边开始编号，从 $1$ 到 $n$。WE 街道从最南边开始编号，从 $1$ 到 $m$。每条第 $i$ 条 NS 街道与第 $j$ 条 WE 街道的交点用一对数字 $(i,j)$ 表示（$1\le i\le n$，$1\le j\le m$）。 字节市有一条公交线路，交叉点作为公交车站。公交车从 $(1,1)$ 交点开始行程，并在 $(n,m)$ 交点结束。此外，公交车只能向东和/或向北行驶。 在一些交叉点有乘客在等车。公交车司机希望选择一条路线，使他能够尽可能多地接到这些乘客。（我们假设公交车内部空间足够大，可以接收所有等待的乘客，无论选择哪条路线。）任务编写一个程序： 从标准输入读取道路网络的描述和每个交叉点等待的乘客人数，找到公交车最多能接到多少乘客，将结果写入标准输出。

标准输入的第一行包含三个正整数 $n$，$m$ 和 $k$——分别表示 NS 街道的数量、WE 街道的数量以及乘客等待公交车的交叉点数量（$1\le n\le 10^9$，$1\le m\le 10^9$，$1\le k\le 10^5$）。 接下来的 $k$ 行描述了乘客等待公交车的分布，每个交叉点一行。在第 $(i+1)$ 行有三个正整数 $x_i$，$y_i$ 和 $p_i$，用单个空格分隔，$1\le x_i\le n$，$1\le y_i\le m$，$1\le p_i\le 10^6$。这种形式的三元组表示在交叉点 $(x_i,y_i)$ 有 $p_i$ 名乘客在等待公交车。输入数据中每个交叉点最多描述一次。等待公交车的乘客总数不超过 $1\ 000\ 000\ 000$。

你的程序应在标准输出中写出一行，包含一个整数——公交车可以接到的最多乘客数。

（由 ChatGPT 4o 翻译）