問題文

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

入力例 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