ミングは次世代チャットアプリ ChatChatA を開発した！

ChatChatA を配布したところ、致命的なバグ報告がミングの元に届いた！メッセージを入力する過程で、メッセージの最後の文字が特定の文字であるとき、特定の文字を入力するとメッセージが「2倍」になるというのだ！

正確に説明すると、「2倍」になるとは次の通りである。

• 現在入力中のメッセージを $M$、$M$ の最後の文字を $s$、入力する文字を $c$ とする。
• メッセージが「2倍」になる $(s, c)$ の組の集合を $D$ とする。
  • $ (s, c) \in D $ の場合、$c$ を入力すると $M$ は $M + c$ ではなく $M + M + c$ になる！
  • $ (s, c) \notin D $ の場合、$c$ を入力すると $M$ は $M + c$ になる。
• $M$ が空文字列の場合、$M$ は「2倍」にならない。

ChatChatA のユーザーであるグミンは、文字列 $T$ を入力するための最小の入力回数が知りたくなった。

現在のメッセージ $M$ は空文字列から始まり、各入力は以下の2つの動作のうちいずれかである。

• $M$ に文字 $c$ を追加する。上記の条件に従って、メッセージが「2倍」になることがある。
• $M$ の最後の文字を削除する。ただし、$M$ が空文字列でない場合にのみこの動作を選択できる。

現在のメッセージ $M$ を $T$ にするための最小の入力回数を、グミンに代わって求めてほしい！

入力

最初の行に $D$ のサイズ $N$ が与えられる。($1 \le N \le 676 = 26^2$)

2行目に長さ $N$ の英小文字列 $S$、3行目に長さ $N$ の英小文字列 $C$ が与えられる。

$S$ の $i$ 文字目を $S_i$、$C$ の $i$ 文字目を $C_i$ とすると、$D=\{(S_i, C_i) : 1 \le i \le N\}$ である。

$|D|=N$ である。すなわち、同じ $(S_i, C_i)$ の組は与えられない。

4行目に、入力する英小文字からなる文字列 $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