AT_abc261_g [ABC261G] Replace

给定两个仅由小写英文字母组成的字符串 $S$ 和 $T$。 高桥君从字符串 $S$ 开始，可以任意多次重复选择以下 $K$ 种操作中的一种进行操作。 第 $i$ 种操作的形式如下： > 支付 $1$ 的代价。然后，如果字符串中包含**字符** $C_i$，则选择其中一个 $C_i$，将其替换为**字符串** $A_i$。如果不包含，则什么也不做。 请你求出将字符串 $S$ 变为与 $T$ 完全相同所需的最小总代价。如果无法变为 $T$，则输出 $-1$。

输入以如下格式从标准输入读入。 > $S$ $T$ > $K$ > $C_1$ $A_1$ > $C_2$ $A_2$ > $\vdots$ > $C_K$ $A_K$

输出将 $S$ 变为 $T$ 所需的最小总代价。如果无法变为 $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)$ 均不同 ## 样例解释 1 高桥君从 $S=$`ab` 开始，可以通过如下 $4$ 次操作将其变为 $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 \to aaa \to aaaaa`，总代价为 $2$，且这是最小值。 ## 样例解释 3 无论如何操作，都无法将 $S=$`a` 变为 $T=$`z`。 由 ChatGPT 4.1 翻译