题目描述

给定两个由小写英文字母组成的字符串 $S$ 和 $T$。

高桥从字符串 $S$ 开始。他可以任意次数以任意顺序执行 $K$ 种操作。第 $i$ 个操作如下：

支付代价 $1$。然后，如果当前字符串中包含字符 $C_i$，选择其中一个出现的位置，并用字符串 $A_i$ 替换它。否则，什么也不做。

找出使字符串变为 $T$ 所需的最小总代价。如果无法实现，则输出 $-1$。

约束条件

• $1\leq |S|\leq |T|\leq 50$
• $1\leq K\leq 50$
• $C_i$ 是 a、b，$\ldots$、或 z。
• $1\leq |A_i|\leq 50$
• $S$、$T$ 和 $A_i$ 是由小写英文字母组成的字符串。
• 将 $C_i$ 视为长度为 $1$ 的字符串，则 $C_i\\neq A_i$。
• 所有的 $(C_i,A_i)$ 对都是不同的。

输入

输入从标准输入给出，格式如下：

$S$ $T$ $K$ $C_1$ $A_1$ $C_2$ $A_2$ $\vdots$ $C_K$ $A_K$

输出

输出使字符串变为 $T$ 所需的最小总代价。如果无法实现，则输出 $-1$。

示例1

ab
cbca
3
a b
b ca
a efg

示例输出1

4

从 $S=$ab 开始，高桥可以按如下方式使用四次操作使得 $T=$cbca：

• 将 ab 中的第 $1$ 个字符 a 替换为 b（第 $1$ 种操作）。现在字符串变为 bb。
• 将 bb 中的第 $2$ 个字符 b 替换为 ca（第 $2$ 种操作）。现在字符串变为 bca。
• 将 bca 中的第 $1$ 个字符 b 替换为 ca（第 $2$ 种操作）。现在字符串变为 caca。
• 将 caca 中的第 $2$ 个字符 a 替换为 b（第 $1$ 种操作）。现在字符串变为 cbca。

每次操作都需要支付代价 $1$，总共支付 $4$，这是最小的可能代价。

示例2

a
aaaaa
2
a aa
a aaa

示例输出2

2

两次操作 a $\\to$ aaa $\\to$ aaaaa 总共支付代价 $2$，这是最小的可能代价。

示例3

a
z
1
a abc

示例输出3

-1

无法通过操作将 $S=$a 变为 $T=$z。