Problem Description

Maddy found a brand-new sword, and she decided to decorate it with some gems. In the mysterious Celeste Mountain region, there are $C$ distinct gems scattered around.
Maddy wants her sword to look very colorful, so she needs to decorate it with at least $k$ gems.
Before setting off, she got a map that records detailed information about the Celeste Mountain region:

• The Celeste Mountain region is divided into an $n \times m$ grid, and each cell is labeled with coordinates from $(1,1)$ to $(n, m)$.
• For a cell at $(i, j)$, its adjacent cells are $(i+1, j)$, $(i-1, j)$, $(i, j+1)$, and $(i, j-1)$. Note that an adjacent cell must also be inside the Celeste Mountain region, i.e., its coordinates must satisfy $1 \le i \le n$, $1 \le j \le m$.
• Each cell is one of the following terrains: land, water, or lava.
• Among them, $C$ cells contain gems, and gems can only appear in cells whose terrain is land or water.

Maddy starts from a given cell $S$. She needs to collect at least $k$ gems in this region. Her actions consume stamina, and the rules for movement and stamina cost are as follows:

• Maddy initially stays at the given cell $S$. It is guaranteed that this cell is land or water and contains no gem.
• Each time, Maddy can move to an adjacent cell whose terrain is land or water; she cannot enter lava cells.
• If both the starting cell and the destination cell of this move are land, then this move costs no stamina.
• Otherwise (i.e., the move involves water, whether starting from water, moving into water, or water $\leftrightarrow$ water), this move costs 1 stamina point.

Please tell Maddy the minimum stamina cost $stm$ required to collect at least $k$ gems, or tell her that it is impossible to collect $k$ gems.

Input Format

The first line contains an integer $T$ ($1 \le T \le 100$), the number of testdata.
For each test case, the first line contains four integers $n, m, C, k$ ($1 \le n, m \le 2 \times 10^3$, $1 \le k \le C \le 15$), representing the grid height and width, the total number of gems on the map, and the number of gems Maddy needs.
The next line contains two integers $S_x$ and $S_y$ ($1 \le S_x \le n$, $1 \le S_y \le m$), representing the row and column coordinates of Maddy's starting position.
Then follow $n$ lines, each a string of length $m$, $S_1, S_2, \dots, S_n$, where $S_i = s_{i,1}s_{i,2}\dots s_{i,m}$ describes the terrain of each cell in row $i$. For any $1 \le i \le n$, $1 \le j \le m$:

• If $s_{i,j} = 0$, the cell is land.
• If $s_{i,j} = 1$, the cell is water.
• If $s_{i,j} = 2$, the cell is lava.

Then there are $C$ lines, each containing two integers $x, y$ ($1 \le x \le n$, $1 \le y \le m$), indicating the coordinates of a cell containing a gem.
It is guaranteed that, within each test case, all gem positions and Maddy's starting position are not on lava, and all these coordinates are pairwise distinct. It is guaranteed that the sum of $n \cdot m$ over all testdata does not exceed $4 \times 10^6$, and at most 5 test cases satisfy $C > 10$.

Output Format

For each test case:

• If Maddy can collect at least $k$ gems, output one integer $stm$ per line, the minimum stamina cost required.
• Otherwise, output one integer $-1$ per line.

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

Hint

Explanation for Sample 1

For Sample 1, the diagram is as follows:

:::align{center} :::

A path achieving the answer is $(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)$.

Translated by ChatGPT 5