Горіховий рядок#11265

Горіховий рядок

2 секунди

256 мегабайтів

Середня

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

Материк, на якому зараз знаходиться Скрат, можна уявити як прямокутне поле розміром $n \times m$ n \times m. Рядки поля пронумеровані від $1$ до $n$ зверху вниз, а стовпці — від $1$ до $m$ зліва направо. Клітинка $(x, y)$ знаходиться на перетині рядка $x$ і стовпця $y$ . Спочатку Скрат знаходиться у клітинці $(x_{0}, y_{0})$ (x_0, y_0). У клітинці з координатами $(i, j)$ можна знайти лише горіхи виду $a_{i, j}$ a_{i, j} (у необмеженій кількості). Пересуватись можна тільки між сусідніми по стороні клітинками; кожен рух займає рівно одну одиницю часу.

Скрат дуже принциповий, тому збирає горіхи саме в тому порядку, в якому вони задані рядком $s$ (тобто, якщо $s = "ab"$ s = \text{"ab"}, то не можна спочатку підняти горіх виду 'b', а потім виду 'a'). Допоможіть визначити мінімальний час, за який Скрат може зібрати всю колекцію. На підняття горіха у клітинці, де Скрат знаходиться, час не витрачається.

Вхідні дані

У першому рядку задано два цілих числа $n$ і $m$ ( $1 \leq n, m \leq 300$ 1 \leq n, m \leq 300) — розміри материка. У другому рядку задано два цілих числа $x_{0}$ x_0 і $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) — координати клітинки, в якій Скрат знаходиться спочатку.

Кожен із наступних $n$ рядків складається рівно з $m$ маленьких англійських літер. У $i$ -му з цих рядків $j$ -й символ задає $a_{i, j}$ a_{i, j} — тип горіхів, які ростуть у клітинці материка $(i, j)$ . Гарантується, що кожен вид горіхів присутній хоча б у одній клітинці материка.

У наступному рядку задано рядок $s$ ( $1 \leq ∣ s ∣ \leq 300$ 1 \leq |s| \leq 300) маленьких англійських літер, що задає послідовність видів горіхів в ідеальній колекції.

Вихідні дані

Виведіть мінімальний час, що потрібний Скрату для збору всієї колекції.

Приклади

Приклад 1

Приклад 2

Примітка

Пояснення до першого прикладу:Оптимальний маршрут — дійти до '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)$ .