Nut's string#11265

Nut's string

2 seconds

256 megabytes

Medium

Squirrel Scrat has grown old and wise. Instead of chasing after just one nut, he now wants to collect a collection of different types of nuts. There are a total of 26 different types of nuts, labeled with the symbols from 'a' to 'z'. The ideal collection that Scrat aims to gather is described by the string $s$ , where the $i$ -th character indicates the type of the $i$ -th nut in the collection.

The continent Scrat is on can be thought of as a rectangular field of size $n \times m$ n \times m. Rows of the field are numbered from $1$ to $n$ from top to bottom, and columns from $1$ to $m$ from left to right. The cell $(x, y)$ is the intersection of row $x$ and column $y$ . Initially, Scrat is located in the cell $(x_{0}, y_{0})$ (x_0, y_0). In the cell with coordinates $(i, j)$ , you can find only nuts of type $a_{i, j}$ a_{i, j}, but in infinite quantity. The terrain is arranged so that movement is only possible between adjacent cells sharing a side, and each move takes exactly one unit of time.

Scrat is very principled, so he will collect the nuts exactly in the order given by the string $s$ (in other words, if $s = "ab"$ s = \text{"ab"}, it is not allowed to pick up a nut of type 'b' first and then a nut of type 'a'). Help him determine the minimum time in which he can collect the entire collection. No time is spent picking up a nut in the cell where Scrat currently is.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n, m \leq 300$ 1 \leq n, m \leq 300)---the dimensions of the continent. The second line contains two integers $x_{0}$ x_0 and $y_{0}$ y_0 ( $1 \leq x_{0} \leq n$ 1 \leq x_0 \leq n, $1 \leq y_{0} \leq m$ 1 \leq y_0 \leq m)---the coordinates of the cell where Scrat starts.

Each of the next $n$ lines contains exactly $m$ lowercase English letters. In the $i$ -th of these lines, the $j$ -th character specifies $a_{i, j}$ a_{i, j}, the type of nut that grows in cell $(i, j)$ of the continent. It is guaranteed that every type of nut is present in at least one cell of the continent.

The next line contains a string $s$ ( $1 \leq ∣ s ∣ \leq 300$ 1 \leq |s| \leq 300) of lowercase English letters describing the sequence of nuts in the ideal collection.

Output

Print the minimum time Scrat needs to collect his entire collection.

Examples

Example 1

Example 2

Note

Explanation for Sample 1:The optimal route is to reach 'n' in the first row in $12$ steps, then go down by $1$ and add 'u' and 't', standing consecutively to the right; this requires $4$ more steps.

Explanation for Sample 2:The optimal route corresponds to the points $(4, 4)$ , then 's' at $(5, 5)$ , 'q' at $(3, 5)$ , 'u' at $(5, 3)$ , 'i' at $(6, 4)$ , 'r' at $(4, 5)$ (twice), 'e' at $(4, 6)$ , and 'l' at $(6, 7)$ .