题目描述

Mingyu 开发了新一代聊天应用 ChatChatA。应用发布后出现了一个严重 Bug：输入某些字符时，当前消息会被“加倍”。

设当前正在输入的消息为字符串 $M$，$M$ 的最后一个字符为 $s$，即将输入的字符为 $c$，会触发加倍的字符对集合为 $D$。

• 若 $(s,c)\in D$，输入 $c$ 后，$M$ 不会变成 $M+c$，而会变成

• 若 $(s,c)\notin D$，输入 $c$ 后，$M$ 变成 $M+c$。
• 若 $M$ 为空串，则不会触发加倍。

其中 + 表示字符串连接。

用户想知道，为了输入目标字符串 $T$，最少需要进行多少次输入操作。

初始时 $M$ 为空串。每次输入操作可以选择以下两种行为之一：

1. 向 $M$ 的末尾输入一个字符 $c$。根据上述规则，这次输入可能触发加倍；
2. 删除 $M$ 的最后一个字符。只有当 $M$ 非空时才能执行。

请计算使当前消息 $M$ 最终恰好等于 $T$ 所需的最少操作次数。

输入格式

第一行包含集合 $D$ 的大小 $N$。

第二行包含长度为 $N$ 的小写英文字母串 $S$。

第三行包含长度为 $N$ 的小写英文字母串 $C$。

对于每个 $1\le i\le N$，字符对 $(S_i,C_i)$ 属于集合 $D$，即

保证所有字符对互不相同。

第四行包含由小写英文字母组成的目标字符串 $T$。

输出格式

输出使当前消息变为 $T$ 所需的最少操作次数。

若无法得到 $T$，输出 -1。

样例 1

输入

1
t
a
chatchata

输出

5

样例 2

输入

2
ct
ha
chatchata

输出

-1

样例 3

输入

2
af
bd
aafaaafaafaaafd

输出

8