#216256. [ECUSTPC 2025] 斑斓色彩

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

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

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

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

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

第一行输入一个整数 ()，表示测试数据的数量。
每组测试数据的第一行输入 4 个整数 (，)，分别表示网格的长与宽、地图上共有的宝石数量以及 Maddy 需要的宝石数量。
随后一行输入两个整数 和 (，)，表示 Maddy 的起始位置的横纵坐标。
随后输入 行，每行一个长度为 的字符串 ，其中 描述第 行各子地块的地形。对任意 ，：

• 若 ，表示该子地块为陆地；
• 若 ，表示该子地块为水；
• 若 ，表示该子地块为岩浆。

随后 行，每行输入两个整数 (，)，表示其中一块宝石所位于的子地块坐标。
保证：单组测试数据中所有宝石位置与 Maddy 起始位置均不在岩浆上，且这些坐标两两不同。保证所有测试数据中的 之和不大于 ，且至多有 5 组测试数据满足 。

对于每组测试数据：

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

样例输入 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

样例输出 1

2
-1

样例 1 解释

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

:::align{center} :::

其中答案的路径是 。