B. Орехнительная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Белка Скрэт постарел и набрался мудрости. Вместо того, чтобы гоняться за тем самым орехом, теперь он хочет собрать коллекцию из орехов разных видов. Всего есть $$$26$$$ различных видов орехов, обозначенных символами от 'a' до 'z'. А идеальная коллекция, которую хочет собрать Скрэт, описывается строкой $$$s$$$, $$$i$$$-й символ которой обозначает вид $$$i$$$-го ореха в коллекции.

Материк, на котором сейчас находится Скрэт, можно представить как прямоугольное поле размера $$$n \times m$$$. Пронумеруем строки поля от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы поля от $$$1$$$ до $$$m$$$ слева направо. Клетка $$$(x, y)$$$ находится на пересечении строки номер $$$x$$$ и столбца номер $$$y$$$. Изначально Скрэт находится в клетке $$$(s_x, s_y)$$$. В клетке с координатами $$$(i, j)$$$ можно найти только орехи вида $$$x_{i, j}$$$, но в бесконечно большом количестве. Рельеф материка устроен так, что перемещение возможно только между соседними по стороне клетками и занимает ровно единицу времени.

Скрэт очень принципиальный, поэтому будет собирать орехи именно в том порядке, в котором они заданы строкой $$$s$$$ (иными словами, если $$$s = \text{«\t{ab}»}$$$, то нельзя сначала подобрать орех вида 'b', а затем орех вида 'a'). Помогите ему определить, за какое минимальное время он может собрать всю коллекцию. На то, чтобы подобрать орех в той клетке, в которой сейчас находится Скрэт, время не тратится.

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — размеры материка ($$$1 \le n, m \le 300$$$). Во второй строке даны два целых числа $$$s_x$$$ и $$$s_y$$$ — координаты клетки, в которой Скрэт находится изначально ($$$1 \le s_x \le n$$$, $$$1 \le s_y \le m$$$).

Каждая из следующих $$$n$$$ строк состоит ровно из $$$m$$$ строчных английских букв. В $$$i$$$-й из этих строк $$$j$$$-й символ задает $$$x_{i, j}$$$ — вид орехов, растущих в клетке материка $$$(i, j)$$$. Гарантируется, что каждый вид орехов присутствует хотя бы в одной клетке материка.

В следующей строке дана строка $$$s$$$ из строчных английских букв, задающая последовательность видов орехов в идеальной коллекции ($$$1 \le |s| \le 300$$$).

Выходные данные

Выведите единственное число — минимальное время, которое потребуется Скрэту, чтобы собрать свою коллекцию.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыОграничения Необходимые подзадачи Информация о проверке
110$$$n, m, |s| \leqslant 10$$$первая ошибка
220$$$n, m \leqslant 10$$$, $$$|s| \leqslant 100$$$1первая ошибка
330$$$n, m, |s| \leqslant 100$$$1, 2первая ошибка
440Без дополнительных ограничений1, 2, 3первая ошибка
Примеры
Входные данные
2 26
1 1
abcdefghijklmnopqrstuvwxyz
abtxyzutalkhfdyutxzbzhhawj
nut
Выходные данные
17
Входные данные
7 7
4 4
abcdefg
xyzabch
wnopqdi
vmvwrej
ulutsfk
tkjihgl
srqponm
squirrel
Выходные данные
17
Примечание

В первом примере оптимальный маршрут — дойти до 'n' в первой строке за $$$12$$$ шагов, затем спуститься вниз на $$$1$$$ и добавить 'u' и 't', стоящие подряд справа, что потребует еще $$$4$$$ шага.

Во втором примере оптимальный маршрут задается точками $$$(4, 4)$$$, 's'$$$(5, 5)$$$, 'q'$$$(3, 5)$$$, 'u'$$$(5, 3)$$$, 'i'$$$(6, 4)$$$, 'r'$$$(4, 5)$$$ (дважды), 'e'$$$(4, 6)$$$ и 'l'$$$(6, 7)$$$.