配点 : 100 点
問題文
A 和
按字典顺序比较 B 长度为几的字符串 S 和
按字典顺序比较 T 。
对于
下面 2 种操作,0 考虑进行任意次数的操作,可以按任意顺序进行。
- S 中的任意位置
插入
AB插入。成本为 X 需要。 - S 中的任意位置
插入
BA插入。成本为 Y 需要。
此外,插入也可以在开头或结尾进行。
S 该值应乘以 T 判断是否可以与之匹配,如果可能,请求出所需的总成本的最小值。
制約
- 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 X Y
出力
S 该值应乘以 T 如果可以与之匹配,所需的总成本的最小值为 1 行输出。如果不可能
输出 -1 。
入力例 1
AB ABAABB 5 3
出力例 1
8
一开始,
在第S = AB 通过以下操作可以实现。S 该值应乘以 T= ABAABB 。
替换为
- S =
AB可以得到第 1 信和 将其重写为 2 在字符之间BA。 由S =ABAB变为。 - S =
ABAB可以得到第 3 信和 将其重写为 4 在字符之间AB。 由S =ABAABB变为。
在这种情况下,所需成本的总和为 3 + 5 = 8 。实际上,这也是所需总成本的最小值。
入力例 2
AAAAAA AAAAAA 2 3
出力例 2
0
入力例 3
AAAAA BBBBBBB 9982 44353
出力例 3
-1
入力例 4
AAABBABABBBBBBABBABBA AAABABBABABBABBBBBABBBBBAAAAABBABABBAABBA 1 100000
出力例 4
300007