밍구 stworzył nowej generacji aplikację czatową ChatChatA!

Po wdrożeniu ChatChatA, do 밍구 trafił krytyczny raport o błędzie! Podczas wpisywania wiadomości, gdy ostatnim znakiem wiadomości jest określony znak, a następnie wpisze się inny określony znak, wiadomość zostaje „podwojona"!

Dokładniej, „podwojenie" oznacza następujące:

• Niech $M$ będzie aktualnie wpisywaną wiadomością, $s$ jej ostatnim znakiem, a $c$ znakiem, który ma zostać wpisany.
• Niech $D$ będzie zbiorem par $(s, c)$, które powodują „podwojenie" wiadomości.
  • Jeśli $(s, c) \in D$, to po wpisaniu $c$ wiadomość $M$ staje się $M + c$, ale $M + M + c$!
  • Jeśli $(s, c) \notin D$, to po wpisaniu $c$ wiadomość $M$ staje się $M + c$.
• Jeśli $M$ jest pustym ciągiem, $M$ nie ulega „podwojeniu".

Użytkownik ChatChatA, Guming, chce wiedzieć, jaka jest minimalna liczba wejść potrzebna do wpisania ciągu $T$.

Na początku wiadomość $M$ jest pusta, a każde działanie to jedna z dwóch czynności:

• Dodaj znak $c$ do $M$. Zgodnie z powyższym warunkiem wiadomość może ulec „podwojeniu".
• Usuń ostatni znak $M$. Tę czynność można wybrać tylko wtedy, gdy $M$ nie jest pusty.

Pomóż Gumingowi znaleźć minimalną liczbę wejść potrzebną, aby aktualna wiadomość $M$ stała się równa $T$!

Wejście

W pierwszym wierszu podany jest rozmiar $N$ zbioru $D$ ($1 \le N \le 676 = 26^2$).

W drugim wierszu podany jest ciąg $S$ złożony z $N$ małych liter angielskiego alfabetu, a w trzecim wierszu ciąg $C$ złożony z $N$ małych liter angielskiego alfabetu.

Jeśli $i$-ty znak $S$ oznaczymy jako $S_i$, a $i$-ty znak $C$ jako $C_i$, to $D = \{(S_i, C_i) : 1 \le i \le N\}$.

$|D| = N$. Oznacza to, że nie występują powtarzające się pary $(S_i, C_i)$.

W czwartym wierszu podany jest ciąg $T$ złożony z małych liter angielskiego alfabetu, który ma zostać wpisany ($1 \le |T| \le 500\,000$).

Wyjście

W pierwszym wierszu wypisz minimalną liczbę wejść potrzebną do utworzenia wiadomości $T$.

Jeśli nie jest możliwe utworzenie wiadomości $T$, wypisz $-1$.

Przykład

Wejście 1

1
t
a
chatchata

Wyjście 1

5

Wejście 2

2
ct
ha
chatchata

Wyjście 2

-1

Wejście 3

2
af
bd
aafaaafaafaaafd

Wyjście 3

8