You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面描述

给定两个字符串 $S$ 和 $T$，Arisa 觉得 $S$ 不好看，想把它变成 $T$。

她可以进行 $K$ 种操作，对于第 $i$ 种操作，她可以花费 $1$ 的代价，把 $S$ 中的一个字母 $C_i$ 用字符串 $A_i$ 替换。

她想知道她能不能把 $S$ 变为 $T$，如果可以，她想知道最小的代价是多少。

输入格式

第一行一个字符串 $S$；

第二行一个字符串 $T$；

第三行一个整数 $K$；

第四至 $K + 3$ 行，第 $i + 3$ 行两个整数 $C_i,A_i$。

输出格式

如果可以，输出最小代价；否则输出 -1。

样例

输入 1

ab
cbca
3
a b
b ca
a efg

输出 1

4

样例 1 解释

输入 2

a
aaaaa
2
a aa
a aaa

输出 2

2

样例 2 解释

a $\to$ aaa $\to$ aaaaa，共花费代价为 $2$。

输入 3

a
z
1
a abc

输出 3

-1

数据范围

• $1 \leq |S| \leq |T| \leq 50$
• $1 \leq K \leq 50$
• $C_i$ 是小写字母
• $1 \leq |A_i| \leq 50$
• $S,T,A_i$ 均由小写字母组成
• $|A_i| = 1$ 时，$C_i \neq A_i$（把 $C_i$ 当成长度为 $1$ 的字符串）
• $(C_i,A_i)$ 互不相同