Мингу разработал чат-приложение нового поколения ChatChatA!
После развертывания ChatChatA Мингу получил сообщение о критической ошибке! Оказалось, что при вводе сообщения, если последний символ сообщения является определённым символом, то при вводе другого определённого символа сообщение "удваивается"!
Если объяснить точнее, то "удваивание" означает следующее:
- Пусть текущее сообщение — $M$, его последний символ — $s$, а символ, который вводится — $c$.
- Обозначим множество пар $(s, c)$, при которых сообщение "удваивается", как $D$.
- Если $ (s, c) \in D $, то при вводе $c$ сообщение $M$ становится не $M + c$, а $M + M + c$!
- Если $ (s, c) \notin D $, то при вводе $c$ сообщение $M$ становится $M + c$.
- Если $M$ — пустая строка, то "удваивания" не происходит.
Пользователь ChatChatA Гумин заинтересовался, какое минимальное количество вводов необходимо, чтобы получить строку $T$.
Изначально сообщение $M$ пусто. Каждое действие — одно из двух:
- Добавить в $M$ символ $c$. В зависимости от условия выше сообщение может "удвоиться".
- Удалить последний символ $M$. Это действие можно выполнить только если $M$ не пусто.
Помогите Гумину найти минимальное количество действий, чтобы текущее сообщение $M$ стало равно $T$!
Входные данные
В первой строке дано число $N$ — размер $D$. ($1 \le N \le 676 = 26^2$)
Во второй строке дана строка $S$ из $N$ строчных латинских букв, в третьей строке — строка $C$ из $N$ строчных латинских букв.
Если обозначить $i$-й символ $S$ за $S_i$, а $i$-й символ $C$ за $C_i$, то $D=\{(S_i, C_i) : 1 \le i \le N\}$.
$|D|=N$. То есть одинаковых пар $(S_i, C_i)$ не встречается.
В четвертой строке дана строка $T$, состоящая из строчных латинских букв. ($1 \le |T| \le 500\,000$)
Выходные данные
В первой строке выведите минимальное количество вводов, необходимое, чтобы сделать текущее сообщение равным $T$.
Если сделать текущее сообщение равным $T$ невозможно, выведите $-1$.
Примеры
Входные данные 1
1 t a chatchata
Выходные данные 1
5
Входные данные 2
2 ct ha chatchata
Выходные данные 2
-1
Входные данные 3
2 af bd aafaaafaafaaafd
Выходные данные 3
8