题目描述

给定一个 $n\times m$ 的网格，有 $k$ 个公交站牌，每个公交站牌有若干名游客等公交。

公交车从 $1,1$ 出发，每次只能向右或向下前进，最后到达终点站 $n,m$。

作为公交车司机，你希望搭载更多的乘客，你需要求出搭载乘客的最多数量。

输入格式

第一行输入三个空格隔开的整数 $n,m,k$，($1\le n\le 10^9$, $1\le m\le 10^9$, $1\le k\le 10^5$)。

接下来 $k$ 行每行三个整数 $x_i,y_i,k_i$ 代表第 $i$ 个公交站牌的位置以及等车的人数, $1\le x_i\le n$,$1\le y_i\le m$,$1\le p_i\le 10^6$。

保证等车的总人数不超过 $1\ 000\ 000\ 000$.

输出格式

输出一个整数代表可以接到的乘客数量的最大值。

8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2

11