Белка Скрэт постарел и набрался мудрости. Вместо того, чтобы гоняться за тем самым орехом, теперь он хочет собрать коллекцию из орехов разных видов. Всего есть $$$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$$$).
Выведите единственное число — минимальное время, которое потребуется Скрэту, чтобы собрать свою коллекцию.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | $$$n, m, |s| \leqslant 10$$$ | первая ошибка | |
| 2 | 20 | $$$n, m \leqslant 10$$$, $$$|s| \leqslant 100$$$ | 1 | первая ошибка |
| 3 | 30 | $$$n, m, |s| \leqslant 100$$$ | 1, 2 | первая ошибка |
| 4 | 40 | Без дополнительных ограничений | 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)$$$.
