Minggu a développé l'application de chat de nouvelle génération ChatChatA !

Après avoir déployé ChatChatA, un rapport de bug critique lui est parvenu ! Lors de la saisie d'un message, si le dernier caractère du message est un certain caractère, taper un certain caractère fait « doubler » le message !

Pour être précis, « doubler » signifie ce qui suit.

• Soit $M$ le message en cours de saisie, $s$ le dernier caractère de $M$, et $c$ le caractère à saisir.
• Soit $D$ l'ensemble des couples $(s, c)$ qui font « doubler » le message.
  • Si $(s, c) \in D$, alors en tapant $c$, $M$ devient $M + M + c$ au lieu de $M + c$ !
  • Si $(s, c) \notin D$, alors en tapant $c$, $M$ devient $M + c$.
• Si $M$ est la chaîne vide, $M$ ne « double » pas.

L'utilisateur de ChatChatA, Gumingi, veut connaître le nombre minimal de saisies pour taper la chaîne $T$.

Le message $M$ commence comme une chaîne vide, et chaque saisie est l'une des deux actions suivantes.

• Ajouter un caractère $c$ à $M$. Selon la condition ci-dessus, le message peut « doubler ».
• Supprimer le dernier caractère de $M$. Cette action n'est possible que si $M$ n'est pas la chaîne vide.

Aide Gumingi à trouver le nombre minimal de saisies pour que le message $M$ devienne $T$ !

Entrée

La première ligne contient la taille $N$ de $D$. ($1 \le N \le 676 = 26^2$)

La deuxième ligne contient une chaîne $S$ de longueur $N$ composée de lettres minuscules anglaises, et la troisième ligne contient une chaîne $C$ de longueur $N$ composée de lettres minuscules anglaises.

En notant $S_i$ le $i$-ème caractère de $S$ et $C_i$ le $i$-ème caractère de $C$, on a $D = \{(S_i, C_i) : 1 \le i \le N\}$.

$|D| = N$. Autrement dit, aucune paire $(S_i, C_i)$ n'est donnée deux fois.

La quatrième ligne contient une chaîne $T$ composée de lettres minuscules anglaises. ($1 \le |T| \le 500\,000$)

Sortie

Afficher sur la première ligne le nombre minimal de saisies nécessaires pour que le message devienne $T$.

S'il est impossible de faire devenir le message $T$, afficher $-1$.

Exemples

Entrée 1

1
t
a
chatchata

Sortie 1

5

Entrée 2

2
ct
ha
chatchata

Sortie 2

-1

Entrée 3

2
af
bd
aafaaafaafaaafd

Sortie 3

8