Minggu has developed the next-generation chat app ChatChatA!

After deploying ChatChatA, a critical bug report came to Minggu! During the process of typing a message, when the last character of the message is a specific character and a specific character is entered, the message becomes "doubled"!

To explain precisely, "doubling" means the following.

• Let the current message be $M$, the last character of $M$ be $s$, and the character to be input be $c$.
• Let $D$ be the set of $(s, c)$ pairs that cause the message to "double".
  • If $(s, c) \in D$, then when $c$ is input, $M$ becomes $M + M + c$ instead of $M + c$!
  • If $(s, c) \notin D$, then when $c$ is input, $M$ becomes $M + c$.
• If $M$ is the empty string, $M$ does not "double".

Guming, a user of ChatChatA, became curious about the minimum number of inputs needed to type the string $T$.

The current message $M$ starts as an empty string, and each input is one of the following two actions.

• Add a character $c$ to $M$. The message may double according to the condition above.
• Delete the last character of $M$. However, this action can only be chosen when $M$ is not empty.

Help Guming find the minimum number of inputs required to make the current message $M$ become $T$!

Input

The first line contains $N$, the size of $D$. ($1 \le N \le 676 = 26^2$)

The second line contains a string $S$ of length $N$ consisting of lowercase English letters, and the third line contains a string $C$ of length $N$ consisting of lowercase English letters.

Let the $i$-th character of $S$ be $S_i$, and the $i$-th character of $C$ be $C_i$. Then $D = \{(S_i, C_i) : 1 \le i \le N\}$.

$|D| = N$. That is, no identical $(S_i, C_i)$ pair is given.

The fourth line contains a string $T$ consisting of lowercase English letters. ($1 \le |T| \le 500\,000$)

Output

Output the minimum number of inputs required to make the current message become $T$ on the first line.

If it is impossible to make the current message become $T$, output $-1$.

Examples

Input 1

1
t
a
chatchata

Output 1

5

Input 2

2
ct
ha
chatchata

Output 2

-1

Input 3

2
af
bd
aafaaafaafaaafd

Output 3

8