#P18359. Insert AB or BA
Insert AB or BA
Insert AB or BA
题目描述
给定两个仅由字符 A 和 B 组成的字符串 、。
你可以按任意顺序,进行任意次以下两种操作,也可以不进行操作:
- 在 的任意位置插入字符串
AB,代价为 。 - 在 的任意位置插入字符串
BA,代价为 。
插入位置也可以是字符串的最前面或最后面。每次操作都针对当前字符串。
判断能否通过这些操作把 变成 。如果可以,求最小总代价。
输入格式
第一行两个字符串 、,用一个空格隔开。
第二行两个整数 、,分别表示插入 AB 和插入 BA 的代价。
输出格式
如果可以把 变成 ,输出最小总代价;否则输出 。
数据范围
- 、 仅由字符
A、B组成。 - 。
- 、 是整数,且 。
- 每个输入文件只有一组数据。
样例输入 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
样例解释
样例 1 中,从 AB 出发,先在第 1、2 个字符之间插入 BA,得到 ABAB;再在当前字符串第 3、4 个字符之间插入 AB,得到 ABAABB。总代价为 ,可以证明这是最小值。