给定一个大小为 $N \times M$ 的网格。你需要从单元格 $(1, 1)$ 移动到 $(N, M)$。你可以从当前位置移动到周围 8 个相邻单元格中的任意一个。某些单元格中存在地雷。当任何地雷爆炸时，它会杀死站在该单元格或该地雷周围 4 个相邻单元格（上、下、左、右）中的任何人。踏入这五个单元格中的任何一个都会触发地雷并导致其爆炸。
你可以根据需要建造和使用任意数量的扩散器。此外，你可以多次使用同一个扩散器。你需要将扩散器直接放置在有地雷的单元格上以将其消除。一旦消除，该地雷将不再构成威胁，且未来永远不会爆炸。建造扩散器和重复使用扩散器都有各自的成本。
在任何时候，当你处于安全单元格（即没有未消除的地雷，且不在任何相邻的未消除地雷的爆炸范围内）时，你可以建造一个扩散器并将其放置在当前位置周围 8 个相邻单元格中的任意一个。
为了重复使用扩散器，你需要移动到它所在的单元格。然后你可以拿起扩散器并携带它移动。当你携带扩散器时，你将无法建造新的扩散器或拿起另一个扩散器。在任何时候，如果你携带了扩散器，且当前位置的 8 个相邻单元格中包含地雷，你可以将扩散器部署到该单元格。如果一个单元格没有地雷，你不能将扩散器放置在那里。每次重复使用扩散器时，都有一个相关的固定成本。此外，当你携带扩散器从一个单元格移动到相邻单元格时，网格上的每个单元格都有其特定的成本。但是，将扩散器放置在相邻单元格中不会产生携带扩散器移动的单元格成本。因此，运输和部署扩散器的总成本将是此固定成本与移动过程中产生的单元格成本之和。
现在你需要找到到达单元格 $(N, M)$ 的最便宜路径。保证网格中没有任何地雷会攻击单元格 $(1, 1)$。此外，保证没有任何单个单元格会被两个不同的地雷攻击。
输入格式
第一行包含一个整数 $T(1 \le T)$。每个测试用例的第一行包含四个整数 $N, M(2 \le N, M \le 1000, N \cdot M \le 10^5)$，$X(1 \le X \le 10^9)$ 和 $Y(1 \le Y \le 10^9)$。其中 $N$ 和 $M$ 表示网格的维度（$N \times M$），$X$ 是建造扩散器的成本，$Y$ 是重复使用扩散器的固定成本。接下来的 $N$ 行包含一个字符串，每行长度为 $M$。每个字符要么是 ‘.’（ASCII 码 46），表示安全单元格；要么是 ‘#’（ASCII 码 35），表示该单元格上有地雷。随后有 $N$ 行，每行包含 $M$ 个整数 $V_{ij}(0 \le V_{ij} \le 10^9)$，其中每个 $V_{ij}$ 表示携带扩散器移动到相邻单元格时，单元格 $(i, j)$ 产生的相关成本。
保证所有测试用例中 $N \cdot M$ 的总和不超过 $10^5$。
输出格式
对于每个测试用例，输出从 $(1, 1)$ 到 $(N, M)$ 的最便宜成本。
样例
样例输入 1
2 3 4 10 5 .... .#.. ...# 0 0 0 0 0 1 2 3 0 0 0 0 3 4 10 10 ..#. .... #..# 0 0 1 0 0 0 0 0 1 0 0 0
样例输出 1
16 20
说明
对于第一个测试用例，我们从单元格 $(1, 1)$ 开始并执行以下步骤：
- 建造一个扩散器（成本 10），将其放置在单元格 $(2, 2)$ 并消除地雷。
- 移动到单元格 $(2, 2)$ 并拿起扩散器（无成本）。
- 携带扩散器移动到单元格 $(2, 3)$（成本 1）。
- 将扩散器放置在单元格 $(3, 4)$ 以重复使用它（成本 5）并消除地雷。
- 最后移动到 $(3, 4)$ 并到达目的地。
总成本为 $(10 + 1 + 5) = 16$。
对于第二个测试用例，我们执行以下步骤：
- 移动到 $(2, 2)$。
- 建造一个扩散器（成本 10），将其放置在单元格 $(1, 3)$ 并消除地雷。
- 移动到单元格 $(2, 3)$。
- 建造一个扩散器（成本 10），将其放置在单元格 $(3, 4)$ 并消除地雷。
- 最后移动到 $(3, 4)$ 并到达目的地。
总成本为 $(10 + 10) = 20$。如果我们想重复使用扩散器，成本至少为 21，因为我们需要携带它移动至少一个单元格。