题目描述

给定一个 $N \times M$ 的网格，其中一些格子被阻塞。网格中有 $C$ 枚硬币，每枚硬币都有一个正整数价值。

网格中还有 $K$ 个传送门，编号为 $1,2,\dots,K$。每个传送门旁边都有一个拉杆，可以用来激活传送门。此外，给定 $K$ 个整数 $A_1,A_2,\dots,A_K$。已知整数 $1,2,\dots,K$ 在序列 $A_1,A_2,\dots,A_K$ 中各恰好出现一次。

你从给定格子 $(Y,X)$ 开始移动。每一步，你可以执行以下操作之一：

• 向右、左、上、下移动一格，但不能进入阻塞格子，也不能走出网格；
• 仅当你位于某个传送门所在格子时，可以拉动该传送门旁边的拉杆。此时，对每个 $i$，所有位于第 $i$ 个传送门格子上的对象（包括你自己和硬币）都会同时通过第三维传送到传送门 $A_i$ 所在的格子。

请计算在遵守上述规则移动时，可以收集到的硬币总价值最大值。移动步数不受限制。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示网格的行数和列数，其中

$1 \le N \cdot M \le 10^5$。

行从上到下编号为 $1,2,\dots,N$，列从左到右编号为 $1,2,\dots,M$。

第二行包含两个整数 $Y$ 和 $X$，表示你的初始位置所在行和列，其中

$1 \le Y \le N,\quad 1 \le X \le M$。

已知该格子不是阻塞格子。

接下来 $N$ 行，每行是一个长度为 $M$ 的字符串，仅由字符 . 和 # 组成。如果第 $i$ 行第 $j$ 个字符是 #，则第 $i$ 行第 $j$ 列的格子被阻塞；否则该格子可通行。

接下来一行包含一个整数 $C$，表示硬币数量，其中

$1 \le C \le 10^5$。

接下来 $C$ 行，第 $i$ 行包含三个整数 $Y_i,X_i,W_i$，表示第 $i$ 枚硬币所在行、列和价值，其中

$1 \le Y_i \le N,\quad 1 \le X_i \le M,\quad 1 \le W_i \le 10^9$。

已知所有硬币位于互不相同的格子上，并且没有硬币位于阻塞格子上。

接下来一行包含一个整数 $K$，表示传送门数量，其中

$1 \le K \le 10^5$。

接下来一行包含 $K$ 个整数 $A_1,A_2,\dots,A_K$，其中

$1 \le A_i \le K$。

再接下来 $K$ 行，第 $i$ 行包含两个整数 $U_i,V_i$，表示第 $i$ 个传送门所在行和列，其中

$1 \le U_i \le N,\quad 1 \le V_i \le M$。

已知所有传送门位于互不相同的格子上，并且没有传送门位于阻塞格子上。

输出格式

输出一个整数：在网格中按照给定规则移动时，可以收集到的硬币总价值最大值。

样例 1

输入

7 8
1 1
...#....
...#....
...#....
#####.##
...#....
.###....
.#.#....
3
5 3 2
7 7 3
7 3 10
4
2 3 4 1
3 3
3 5
5 5
5 3

输出

5

样例解释

我们前往传送门 $1$，然后连续拉动两次拉杆，从而移动到传送门 $3$。与此同时，第一枚硬币一开始与传送门 $4$ 位于同一格，它会先移动到传送门 $1$，再移动到传送门 $2$。现在我们可以前往格子 $(3,5)$，那里是第一枚硬币此时所在的位置，并将其捡起。之后前往格子 $(7,7)$，捡起第二枚硬币。

第三枚硬币位于格子 $(7,3)$，它被墙与网格的其他区域隔开，因此永远无法捡起。最终我们捡起两枚硬币，总价值为 $2+3=5$。

样例 2

输入

5 18
1 2
........##########
........#..#..#..#
#######.##########
#..#..#...........
#######...........
1
2 13 100
7
6 5 4 2 3 7 1
1 1
5 18
2 10
2 13
2 16
4 2
4 5

输出

100

样例解释

本样例中只有一枚硬币，它一开始与传送门 $4$ 位于同一格。传送门 $1$ 和 $2$ 之间可以行走，其余传送门与网格其他部分隔开。

为了得到硬币，我们前往传送门 $1$ 并拉动九次拉杆。我们的位置变化为：

$1 \to 6 \to 7 \to 1 \to 6 \to 7 \to 1 \to 6 \to 7 \to 1$。

硬币同时按如下方式移动：

$4 \to 2 \to 5 \to 3 \to 4 \to 2 \to 5 \to 3 \to 4 \to 2$。

此时我们可以从传送门 $1$ 走到传送门 $2$，并捡起硬币。

评分方式

本题测试点分为以下组。只有通过某组内所有测试，才能获得该组分数：

1. $0$ 分：样例。
2. $5$ 分：$K=1$。
3. $5$ 分：$K=2$，$A_1=2$ 且 $A_2=1$。
4. $20$ 分：$K \le 4$。
5. $20$ 分：$K \le 8$。
6. $5$ 分：$K \le 16$。
7. $5$ 分：$K \le 1000$。
8. $40$ 分：无额外限制。

此外，只有通过前面所有测试组的程序，才能获得第 $4$ 至第 $8$ 组的分数。