Migrated from Lutece 2942 纳米纵连，小子！

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

光光和对立正在玩一款叫做 Project Sekai 的游戏，但是这题和游戏里的纵连没有任何关系。

游戏中有 $m$ 个竖向的轨道，一首歌有 $n$ 拍。（你可以理解为 $m$ 列 $n$ 行的矩阵）

对立邀请你写一张谱面，她给了你一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 个数字 $a_{i,j}$ 表示在第 $i$ 拍将音符放在第 $j$ 个轨道上可获得的难度值。

你选择把谱面塞爆，每拍都放且只放一个音符，这首歌的难度值就是 $n$ 个音符的难度值之和。除此之外，你还想让难度值尽可能大，所以你每拍找了一个难度最大的音符，但是写出来的谱面非常难看。

光想让谱面好看些，她给了你 $k$ 个限制，每个限制有三个整数 $x,y,z$ 表示第 $x$ 拍和第 $y$ 拍的音符横向距离不能超过 $z$（可以等于 $z$ ）。

现在，你想知道在满足 $k$ 个限制的情况下这首歌难度的最大值。

注意到肯定是有方案可以满足的，比如你把所有音符放同一轨道上（音游里称为纵连）。

Input

第一行两个整数 $n,m$，表示拍数和轨道数。

接下来输入一个 $n$ 行 $m$ 列的矩阵，表示每拍每个轨道的难度值。

第 $n+2$ 行一个数 $k$ ，表示有 $k$ 个限制。

接下来 $k$ 行每行三个整数 $x_i,y_i,z_i$ ，含义见题面。

Output

一个整数 $ans$，这个谱面可以写出的最大难度。

Samples

4 5
9 1 7 6 3
9 1 8 6 3
9 7 5 6 3
1 1 1 9 2
3
1 3 2
3 4 1
2 4 0

29

Constraints

$1 \leq n\leq 500$，$1 \leq m \leq 50$，$0 \leq k \leq 500$;

$1 \leq a_{i,j} \leq 1\times 10^5$，$1 \leq x_i \neq y_i \leq n$，$0\leq z_i \leq m-2$。

Note

样例解释：

如果你选择在第一个轨道放个大纵连，你的难度值就是 $9+9+9+1=28$。

如果第一拍选 $9$ ，第二拍选 $6$，第三拍选 $5$，第四拍选 $9$，可以满足所有限制，难度值 $9+6+5+9=29$，是最大值。

Resources

2023 UESTC ICPC Training for Graph