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.
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 a single number — the minimum time required for Scrat to collect his collection.
Points for each subtask are awarded only if all tests for that subtask and the required subtasks are passed.
| Subtask | Points | Constraints | Required Subtasks | Validation Information |
| 1 | 10 | $$$n, m, |s| \leqslant 10$$$ | first error | |
| 2 | 20 | $$$n, m \leqslant 10$$$, $$$|s| \leqslant 100$$$ | 1 | first error |
| 3 | 30 | $$$n, m, |s| \leqslant 100$$$ | 1, 2 | first error |
| 4 | 40 | No additional constraints | 1, 2, 3 | first error |
2 26 1 1 abcdefghijklmnopqrstuvwxyz abtxyzutalkhfdyutxzbzhhawj nut
17
7 7 4 4 abcdefg xyzabch wnopqdi vmvwrej ulutsfk tkjihgl srqponm squirrel
17
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)$$$.
