题目描述

Maddy 找到了一把崭新的剑，她决定用一些宝石装饰她的剑。在神秘的 Celeste 山地区，有 $C$ 块各不相同的宝石散落在各处。
Maddy 希望她的剑看起来非常五彩斑斓，因此她至少需要用 $k$ 块宝石来装饰她的剑。
在出发之前，她拿到了一张地图，地图上记载了 Celeste 山地区的详细情况：

• Celeste 山地区被分为了一个 $n \times m$ 的网格，分别用坐标 $(1,1)$ 到 $(n, m)$ 标记每一子地块的情况。
• 我们称一块坐标为 $(i, j)$ 的子地块的相邻子地块为 $(i+1, j)$、$(i-1, j)$、$(i, j+1)$ 和 $(i, j-1)$；注意相邻子地块亦需要在 Celeste 山地区之中，即相邻子地块的坐标 $(i, j)$ 亦应满足 $1 \le i \le n$，$1 \le j \le m$。
• 每一块子地块的地形为陆地、水或者岩浆。
• 其中 $C$ 个子地块中有宝石，且宝石只可能在地形为陆地或者水的子地块中。

Maddy 从一个给定的子地块 $S$ 出发，她需要在这一区域收集至少 $k$ 块宝石。她的行动需要消耗精力值，行动和精力值的计算规则如下：

• Maddy 初始位于所给定的子地块 $S$，保证这一子地块的地形为陆地或者水且没有宝石。
• Maddy 每次可以移动到一个相邻的、地形为陆地或者水的子地块中；她不能进入岩浆子地块。
• 若本次移动的起点与终点均为 “陆地”，则这次移动不消耗精力值。
• 否则（即本次移动涉及 “水”，无论是从水出发，或移动到水，或水 $\leftrightarrow$ 水），这次移动将会消耗 1 点精力值。

请告诉 Maddy 她至少需要消耗多少精力值 $stm$ 才能收集至少 $k$ 块宝石，或告诉她不可能收集到 $k$ 块宝石。

输入格式

第一行输入一个整数 $T$ ($1 \le T \le 100$)，表示测试数据的数量。
每组测试数据的第一行输入 4 个整数 $n, m, C, k$ ($1 \le n, m \le 2 \times 10^3$，$1 \le k \le C \le 15$)，分别表示网格的长与宽、地图上共有的宝石数量以及 Maddy 需要的宝石数量。
随后一行输入两个整数 $S_x$ 和 $S_y$ ($1 \le S_x \le n$，$1 \le S_y \le m$)，表示 Maddy 的起始位置的横纵坐标。
随后输入 $n$ 行，每行一个长度为 $m$ 的字符串 $S_1, S_2, \dots, S_n$，其中 $S_i = s_{i,1}s_{i,2}\dots s_{i,m}$ 描述第 $i$ 行各子地块的地形。对任意 $1 \le i \le n$，$1 \le j \le m$：

• 若 $s_{i,j} = 0$，表示该子地块为陆地；
• 若 $s_{i,j} = 1$，表示该子地块为水；
• 若 $s_{i,j} = 2$，表示该子地块为岩浆。

随后 $C$ 行，每行输入两个整数 $x, y$ ($1 \le x \le n$，$1 \le y \le m$)，表示其中一块宝石所位于的子地块坐标。
保证：单组测试数据中所有宝石位置与 Maddy 起始位置均不在岩浆上，且这些坐标两两不同。保证所有测试数据中的 $n \cdot m$ 之和不大于 $4 \times 10^6$，且至多有 5 组测试数据满足 $C > 10$。

输出格式

对于每组测试数据：

• 若 Maddy 可以收集到至少 $k$ 块宝石，输出一行一个整数 $stm$，表示她至少需要消耗的精力值；
• 否则输出一行一个整数 $-1$。

2
3 5 3 2
1 1
00000
11211
11011
1 4
3 1
3 5
1 5 1 1
1 1
01121
1 5

2
-1

提示

样例 1 解释

对于第 1 个样例，其示意图如下：

:::align{center} :::

其中答案的路径是 $(1,1) \to (1,2) \to (1,3) \to (1,4) \to (1,3) \to (1,2) \to (1,1) \xrightarrow{1\text{ 精力值}} (2,1) \xrightarrow{1\text{ 精力值}} (3,1)$。