题目背景

“没时间，快决定。行动，还是再次停留。”——次祖伽密·凯尔

题意描述

第四隔离设施的防御阵地是一个 $r\times c$ 的网格。

相邻两个格子之间要么直接相连，要么有不可通过的墙相隔。

整个阵地中，任意两个位置有且仅有一条路径相连。

有 $n$ 太人形兵器把守该阵地，每个格子最多有一个人形兵器，经过该格子之前必须干掉格内的人形兵器。

每台人形兵器可以保护一个或几个人形兵器(可能包含自身)。人形兵器的火力很猛，尝试去攻击一个正在被保护的人形兵器无异于作死。而一个没有被保护的人形兵器则可以被轻易地干掉。

击杀一个人形兵器需要消耗一定的能量，而从其残骸上可以得到一定的能量补充。

现降落在 $(x_0,y_0)$ 并可以在任何地点脱身，要求获取尽可能多的能量。

你可以假设初始能量是足够多的。

输入格式

第一行四个数 $r, c, x_0, y_0$，表示阵地大小和降落地点。

接下来 $r$ 行，每行 $c-1$ 个数，第 $i$ 行第 $j$ 个数表示 $(i, j)$ 与 $(i,j+1)$ 是否有墙相隔。

接下来 $r-1$ 行，每行 $c$ 个数，第 $i$ 行第 $j$ 个数表示 $(i,j)$ 与 $(i+1,j)$ 是否有墙相隔。

下一行两个数 $n,m$，空格分隔，表示人形兵器的数量和保护关系的数量。

接下来 $n$ 行，每行 $3$ 个数 $x_i, y_i, w_i$，表示人形兵器坐标和攻击时带来的能量变化（）负表示需要消耗，正表示可以得到补充）。

接下来 $m$ 行， 每行两个数 $a_i,b_i$，表示编号为 $a_i$ 的人形兵器保护编号为 $b_i$ 的人形兵器。

输入数据保证地图满足要求。注意所有坐标从 $1$ 开始。

输出格式

仅一行，一个数，表示获取的最大能量值。

样例

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

14

看守关系：$+3$ 看守 $-7$，$+9$ 看守 $+4$。

攻击顺序：$+3\to -7\to +9\to +4\to -2\to +7$，撤离。

数据规模与约定

对于 $40\%$ 的数据，$r,c\le 15$，$n\le 15$，$m\le 30$，$|w_i|\le 100$。

对于 $100\%$ 的数据，$1\le r,c\le 10^3$，$0\le n\le 10^4$，$1\le m\le 3\times 10^4$，$|w_i|\le 10^4$。