Description

The map of the Undercity is an $n \times m$ grid of $0/1$. If $a_{i, j} = 1$, then position $(i, j)$ is an obstacle and cannot be traversed; if $a_{i, j} = 0$, then position $(i, j)$ is passable.

Xiao A and Thrall start at $(x_1, y_1)$, and the Dreadlord starts at $(x_2, y_2)$. Xiao A’s goal is to reach the Dreadlord’s position.

Thrall moves according to a specific route, which is a digit string composed of digits $0$ to $4$.

At second $i$:

• If the $i$-th digit (thinking of the digit string repeated infinitely) is $0$, Thrall stays still this second.
• If it is $1$, Thrall moves up by one cell this second.
• If it is $2$, Thrall moves down by one cell this second.
• If it is $3$, Thrall moves left by one cell this second.
• If it is $4$, Thrall moves right by one cell this second.

If Thrall’s next position would be a wall or outside the maze, Thrall stays in place. The Dreadlord follows the same rule. (In other words, you can think of the digit string as repeating infinitely; at second $i$, take the $i$-th character of this infinite string.)

Each second, Xiao A may choose one of the four directions (up, down, left, right) and move one cell in that direction, provided the destination is not a wall and not out of bounds; or Xiao A may stay in place. However, due to the strange environment in the Undercity, Xiao A can remain outside Thrall’s “aura” for at most $s$ consecutive seconds; if this limit is exceeded, Xiao A dies. The aura has effective radius $d$, meaning Xiao A receives Thrall’s aura effect only when the distance $\sqrt{(x-xx)^2+(y-yy)^2}$ between Xiao A and Thrall is less than or equal to $d$. If Xiao A leaves Thrall’s aura and then re-enters the effective area of the aura, the counter resets to zero the next time Xiao A leaves the aura.

Xiao A wants to know the minimum number of seconds needed to reach the Dreadlord’s position.

Input Format

The first line contains four integers $n, m, s, d$.

The next $n$ lines each contain $m$ digits ($0$ or $1$) without spaces, representing the map of the Undercity.

The next line contains four integers $x_1, y_1, x_2, y_2$ ($1 \le x_1, x_2 \le n$, $1 \le y_1, y_2 \le m$).

The next line is a digit string describing Thrall’s movement.

The next line is a digit string describing the Dreadlord’s movement.

Output Format

Output a single integer on one line, the minimum time required.

3 4 7 3
1010
0000
0101
1 2 3 3
0132401
12131

3

Hint

Source: kiro, original.

Constraints: For $100\%$ of the testdata, $1 \le n, m \le 50$, $0 \le s \le 1000$, $0 \le d \le 100$, $1 \le$ length of the digit string $\le 100$, $0 \le$ answer $\le 100$.

Translated by ChatGPT 5