题目背景

校园里有一张 $n$ 行 $m$ 列的打卡图，每个格子都有一定积分。活动开始时，所有格子都可以进入。随着时间推移，部分格子会失效，失效后就不能再进入。

题目描述

你从左上角 $(1,1)$ 出发，每次只能向右或向下移动一格。进入一个格子时，可以获得该格子的积分，每个格子的积分至多获得一次。

系统给出 $t$ 个失效事件。事件 $(x,y,v)$ 表示格子 $(x,y)$ 会在你完成第 $v$ 次移动之前失效，并从那之后不能进入。特别地，即使起点在第一次移动前失效，你仍然可以从起点出发。

请计算在这些限制下最多能获得多少积分。

输入格式

第一行输入两个整数 $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

提示

样例解释

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

数据范围

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

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