题目背景

校园里有一张 $n$ 行 $m$ 列的打卡地图，每个格子都有一定的积分。

活动开始时，所有格子都可以进入。随着移动次数增加，一些格子会在指定时刻失效，失效后的格子不能再进入。

题目描述

你最开始位于左上角 $(1,1)$，并立即获得该格子的积分。

之后每次移动，你只能从当前格子向右或向下移动一格。每当你进入一个格子时，就可以获得该格子的积分。

由于只能向右或向下移动，每个格子最多只会经过一次。

地图中有 $t$ 个格子会在指定时刻失效。

一个失效事件 $(x,y,v)$ 表示： 在进行第 $v$ 次移动之前，格子 $(x,y)$ 会失效。

格子失效后，不能再移动进入该格子。

例如，一个格子在第 $2$ 次移动之前失效，那么：

• 在第 $1$ 次移动结束后到达该格子是允许的；
• 在第 $2$ 次及之后的移动中，都不能再进入该格子。

需要注意的是：

• 如果你在某个格子失效之前已经进入了该格子，那么即使之后该格子失效，你仍然可以从该格子继续向右或向下移动；
• 起点 $(1,1)$ 是特殊的。无论它在何时失效，你都可以从 $(1,1)$ 开始，并获得起点的积分；
• 你不需要一定到达右下角 $(n,m)$。如果没有可以进入的相邻格子，则移动结束。

请计算整个移动过程中最多能够获得多少积分。

输入格式

第一行输入两个整数 $n,m$，表示打卡图大小。

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,j}$，表示每个格子的积分，$1 \le a_{i,j} \le 1000$。

接下来一行输入一个整数 $t$，表示失效事件数量，$1 \le t \le n\times m$。

接下来 $t$ 行，每行三个整数 $x,y,v$，表示一个失效事件，保证所有事件中的 $(x,y)$ 互不相同，且 $1 \le x \le n$，$1 \le y \le m$，$1 \le v \le n\times m$。

输出格式

输出一个整数，表示最多能获得的积分。

样例

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

5

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

1

2 2
1 100
1 100
1
1 1 1

201

提示

样例解释

样例 $1$ 中，第一次移动前 $(1,1)$ 和 $(1,2)$ 失效，但仍允许从起点出发，所以只能向下走到 $(2,1)$。第二次移动前 $(2,2)$ 失效，之后最优路线继续向下再向右，最多获得 $5$ 分。

数据范围

对于 $30\%$ 的数据，$1 \le n,m \le 10$。

对于 $100\%$ 的数据，$1 \le n,m \le 1000$。