给定两个仅由字符 A 和 B 组成的字符串 $S$ 和 $T$。

你可以按任意顺序执行任意次数（包括零次）以下两种操作：

• 在 $S$ 的任意位置插入字符串 AB。该操作的代价为 $X$。
• 在 $S$ 的任意位置插入字符串 BA。该操作的代价为 $Y$。

注意，插入操作也可以在字符串的开头或结尾进行。

请判断是否可以通过这些操作将 $S$ 转换为 $T$。如果可以，输出所需的最小总代价；否则，输出 -1。

输入格式

输入按以下格式给出：

$S \ T$ $X \ Y$

• $X$ 和 $Y$ 为整数。
• $S$ 和 $T$ 仅由字符 A 和 B 组成。
• $1 \le |S| \le |T| \le 8000$。
• $1 \le X \le 10^9$。
• $1 \le Y \le 10^9$。

输出格式

如果可以将 $S$ 转换为 $T$，则在一行中输出所需的最小总代价。如果无法转换，则输出 -1。

样例

样例输入 1

AB ABAABB
5 3

样例输出 1

8

样例输入 2

AAAAAA AAAAAA
2 3

样例输出 2

0

样例输入 3

AAAAA BBBBBBB
9982 44353

样例输出 3

-1

样例输入 4

AAABBABABBBBBBABBABBA AAABABBABABBABBBBBABBBBBAAAAABBABABBAABBA
1 100000

样例输出 4

300007

说明

在第一个样例中，$S = \text{AB}$。你可以通过执行以下操作将 $S$ 转换为 $T = \text{ABAABB}$：

• 在 AB 的第 1 个和第 2 个字符之间插入 BA，得到 ABAB。
• 在 ABAB 的第 3 个和第 4 个字符之间插入 AB，得到 ABAABB。

在这种情况下，总代价为 $3 + 5 = 8$，这是实现该转换所需的最小总代价。