与芭比散步

时间限制：2 秒
内存限制：512 MB
输入：标准输入
输出：标准输出

沙滩是一个 $h \times w$ 的矩形。有 $n$ 个特殊格子。其中一些格子上有巨石，不能进入；其余格子上有有趣的小物件（贝壳、珊瑚等），芭比看到后会增加对肯的好感度。每个格子 $(i,j)$ 有一个权值 $c_{i,j}$，表示经过该格子时好感度的增加量（若为巨石则不可通过）。帮助肯规划最优散步路线，使得最终芭比的好感度最大。

散步从 $(1,1)$ 开始，到 $(h,w)$ 结束。由于芭比时间有限，他们只能向左、向右和向下移动。

输入格式

第一行包含三个整数 $h$, $w$ 和 $n$ ——沙滩的高和宽以及特殊格子的数量（$1 \le h \le 10^5$；$1 \le w \le 10^9$；$1 \le n \le 10^5$）。

接下来 $n$ 行，每行描述一个特殊格子。描述格式为 i j + d，表示格子 $(i,j)$ 上有一个物品，增加好感度 $+d$；或者 i j #，表示格子 $(i,j)$ 上有一个巨石（$1 \le d \le 10^9$）。

输出格式

输出一行一个整数，表示肯最终能获得的最大好感度（初始好感度为 $0$）。

数据保证存在至少一条从 $(1,1)$ 到 $(h,w)$ 的路径。

样例

输入

4 5 11
1 3 + 2
1 5 #
2 2 + 4
2 3 #
3 1 + 1
3 2 + 1
3 4 #
3 5 + 5
4 1 + 10
4 2 #
4 4 + 2

输出

10