收集金币
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}现有一个 n 行 m 列的网格迷宫，每个方格要么是可以通过的空方格，要么是不可通过的墙方格，迷宫的四周边界外都是墙方格。初始时，迷宫中不存在墙方格。
\hspace{15pt}我们使用 (i,j) 表示网格中从上往下数第 i 行和从左往右数第 j 列的方格，里面有 a_{i,j} 个金币。
\hspace{15pt}在开始移动前，小K已经知道了 t 条信息，每条信息以一个三元组 \{x, y, v\} 表示，代表 (x,y) 方格会在第 v 回合永久变成墙方格（在此之前金币仍可收集）。每一回合开始时，方格先发生变化，小K再进行移动（特别地，如果起点在第一回合变为墙方格，视作小K不受影响）。
\hspace{15pt}小K从左上角 (1,1) 方格出发，记当前所在的位置为 (x,y)，每回合只能向右移动一格到达 (x,y+1) 或向下移动一格到达 (x+1,y)。每一个方格中的金币只能收集一次，请问小K最多能收集到多少金币？

输入描述:

\hspace{15pt}第一行输入两个整数 n,m\left(1\le n,m \le 1000\right) 代表迷宫的大小。
\hspace{15pt}此后 n 行，每行输入 m 个整数 a_{i,1},a_{i,2},\dots,a_{i,m} \left(1\le a_{i,j} \le 100\right) 代表每个迷宫方格的金币数量。
\hspace{15pt}第 n+2 行输入一个整数 t \left(1\le t\le n\times m\right) 代表信息条数。
\hspace{15pt}此后 t 行，每行输入三个整数 x,y,v \left(1\le x \le n;\ 1\le y \le m;\ 1\le v \le n \times m\right) 代表一条信息。保证每一条信息的 (x,y) 互不相同。

输出描述:

\hspace{15pt}输出一个整数，代表小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