B. Nutty String
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Scrat the Squirrel has grown old and gained wisdom. Instead of chasing after that same acorn, he now wants to collect a variety of nuts. There are a total of $$$26$$$ different types of nuts, represented by the characters from 'a' to 'z'. The ideal collection that Scrat wants to gather is described by a string $$$s$$$, where the $$$i$$$-th character represents the type of the $$$i$$$-th nut in the collection.

The continent where Scrat is currently located can be represented as a rectangular field of size $$$n \times m$$$. The rows of the field are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right. Cell $$$(x, y)$$$ is located at the intersection of row number $$$x$$$ and column number $$$y$$$. Initially, Scrat is located in cell $$$(s_x, s_y)$$$. In cell $$$(i, j)$$$, only nuts of type $$$x_{i, j}$$$ can be found, but there are an infinite number of them. The terrain of the continent is such that movement is only possible between adjacent cells and takes exactly one unit of time.

Scrat is very particular, so he will collect nuts in the order specified by the string $$$s$$$ (in other words, if $$$s = \text{«\t{ab}»}$$$, it is not possible to first pick up a nut of type 'b', and then a nut of type 'a'). Help him determine the minimum amount of time it will take him to collect the entire collection. No time is spent picking up a nut in the cell where Scrat is currently located.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ — the dimensions of the continent ($$$1 \le n, m \le 300$$$). The second line contains two integers $$$s_x$$$ and $$$s_y$$$ — the coordinates of the cell where Scrat is initially located ($$$1 \le s_x \le n$$$, $$$1 \le s_y \le m$$$).

Each of the following $$$n$$$ lines consists of exactly $$$m$$$ lowercase English letters. The $$$j$$$-th character in the $$$i$$$-th of these lines represents $$$x_{i, j}$$$ — the type of nuts growing in the cell $$$(i, j)$$$ of the continent. It is guaranteed that each type of nut is present in at least one cell of the continent.

The next line contains a string $$$s$$$ consisting of lowercase English letters, representing the sequence of nut types in the ideal collection ($$$1 \le |s| \le 300$$$).

Output

Output a single number — the minimum time required for Scrat to collect his collection.

Scoring

Points for each subtask are awarded only if all tests for that subtask and the required subtasks are passed.

SubtaskPointsConstraints Required Subtasks Validation Information
110$$$n, m, |s| \leqslant 10$$$first error
220$$$n, m \leqslant 10$$$, $$$|s| \leqslant 100$$$1first error
330$$$n, m, |s| \leqslant 100$$$1, 2first error
440No additional constraints1, 2, 3first error
Examples
Input
2 26
1 1
abcdefghijklmnopqrstuvwxyz
abtxyzutalkhfdyutxzbzhhawj
nut
Output
17
Input
7 7
4 4
abcdefg
xyzabch
wnopqdi
vmvwrej
ulutsfk
tkjihgl
srqponm
squirrel
Output
17
Note

In the first example, the optimal route is to reach 'n' in the first row in $$$12$$$ steps, then move down by $$$1$$$ and add 'u' and 't', which are consecutive to the right, requiring an additional $$$4$$$ steps.

In the second example, the optimal route is given by the points $$$(4, 4)$$$, 's'$$$(5, 5)$$$, 'q'$$$(3, 5)$$$, 'u'$$$(5, 3)$$$, 'i'$$$(6, 4)$$$, 'r'$$$(4, 5)$$$ (twice), 'e'$$$(4, 6)$$$, and 'l'$$$(6, 7)$$$.