AT_utpc2024_i Insert AB or BA

`A` と `B` からなる文字列 $ S $ と $ T $ が与えられます。 以下の $ 2 $ 種類の操作を、 $ 0 $ 回以上の好きな回数、好きな順番で行うことを考えます。 - $ S $ の任意の位置に `AB` を挿入する。コストが $ X $ かかる。 - $ S $ の任意の位置に `BA` を挿入する。コストが $ Y $ かかる。 なお、挿入は先頭・末尾に対して行うこともできます。 $ S $ を $ T $ と一致させることが可能かを判定し、可能な場合は必要な合計コストの最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ T $ $ X $ $ Y $

$ S $ を $ T $ と一致させることが可能な場合は、必要な合計コストの最小値を $ 1 $ 行に出力せよ。不可能な場合は `-1` を出力せよ。

### Sample Explanation 1 はじめ、 $ S = $ `AB` です。以下のように操作を行うことで、 $ S $ を $ T= $ `ABAABB` に一致させることができます。 - $ S = $ `AB` の $ 1 $ 文字目と $ 2 $ 文字目の間に `BA` を挿入する。 $ S = $ `ABAB` となる。 - $ S = $ `ABAB` の $ 3 $ 文字目と $ 4 $ 文字目の間に `AB` を挿入する。 $ S = $ `ABAABB` となる。 この場合、かかるコストの合計は $ 3 + 5 = 8 $ となります。実はこれが必要な合計コストの最小値でもあります。 ### Constraints - $ 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 $