现有一个 行 列的网格迷宫，每个方格要么是可以通过的空方格，要么是不可通过的墙方格，迷宫的四周边界外都是墙方格。初始时，迷宫中不存在墙方格。 我们使用 表示网格中从上往下数第 行和从左往右数第 列的方格，里面有 个金币。 在开始移动前，小K已经知道了 条信息，每条信息以一个三元组 表示，代表 方格会在第 回合永久变成墙方格（在此之前金币仍可收集）。每一回合开始时，方格先发生变化，小K再进行移动（特别地，如果起点在第一回合变为墙方格，视作小K不受影响）。 小K从左上角 方格出发，记当前所在的位置为 ，每回合只能向右移动一格到达 或向下移动一格到达 。每一个方格中的金币只能收集一次，请问小K最多能收集到多少金币？
输入描述:
第一行输入两个整数  代表迷宫的大小。此后  行，每行输入  个整数 代表每个迷宫方格的金币数量。第 行输入一个整数 代表信息条数。此后  行，每行输入三个整数 代表一条信息。保证每一条信息的 互不相同。


输出描述:
输出一个整数，代表小K最多能收集到的金币数量。
示例1

输入

3 3
1 100 100
1 100 100
1 1 1
3
1 1 1
1 2 1
2 2 2

输出

5

说明

\hspace{15pt}在这个样例中，我们使用 \Box 表示墙方格，用 \bullet 表示小K当前回合所在的位置。初始时，迷宫状态如公式所示：\begin{bmatrix}<br />\bullet & 100 & 100 \\<br />1 & 100 & 100 \\<br />1 & 1 & 1<br />\end{bmatrix}。

\hspace{15pt}第一回合：由于 (1,2) 会在第一回合变为墙方格，所以他只能走到 (2,1)，第一回合结束时，小K已经得到了 2 个金币，迷宫状态如公式所示：\begin{bmatrix}<br />\Box & \Box & 100 \\<br />\bullet & 100 & 100 \\<br />1 & 1 & 1<br />\end{bmatrix}。

\hspace{15pt}第二回合，小K只能向下移动到 (2,2)，第二回合结束时，小K已经得到了 3 个金币，迷宫状态如公式所示：\begin{bmatrix}<br />\Box & \Box & 100 \\<br /> & \Box & 100 \\<br />\bullet & 1 & 1<br />\end{bmatrix}。

\hspace{15pt}剩余的回合，迷宫不再发生变化，而由于小K只能向下或者右移动，所以他至多收集到 (3,2) 和 (3,3) 两个方格的金币。加起来刚好是 5 个金币。
示例2

输入

3 3
1 100 100
100 100 100
100 100 100
2
2 1 1
1 2 1

输出

1
加载中...