AT_ddcc_2016_final_c 01文字列

[problemUrl]: https://atcoder.jp/contests/ddcc2016-final/tasks/ddcc_2016_final_c 文字列 $ s $ に対して以下の $ 3 $ 種類の操作を何度か行い、文字列 $ T $ を作ることを考えます。 $ s $ ははじめ空文字列です。 1. $ A $ 円払って $ s $ の先頭に`0`を挿入する。 2. $ B $ 円払って $ s $ の末尾に`1`を挿入する。 3. $ C $ 円払って $ s $ に含まれる`0`を全て`1`に、$ s $ に含まれる`1`を全て`0`に置換する。 文字列 $ T $ を作るために必要な資金の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ A $ $ B $ $ C $ $ T $

答えを $ 1 $ 行に出力せよ。

### 制約 - $ 1\ ≦\ A,\ \,\ B,\ \,\ C\ ≦\ 10^{9} $ - $ 1\ ≦\ |T|\ ≦\ 2\ \times\ 10^{5} $ - $ T $ は`0`と`1`のみからなる文字列 - $ A,\ \,\ B,\ \,\ C $ はいずれも整数 ### 部分点 - $ 1≦|T|≦10 $ を満たすデータセットに正解した場合は、$ 300 $ 点が与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 400 $ 点が与えられる。 ### Sample Explanation 1 \- はじめに操作 $ 1 $ を $ 2 $ 回行います。$ s $ は`00`となります。 - 次に操作 $ 3 $ を $ 1 $ 回行います。 $ s $ は`11`となります。 - 最後に操作 $ 1 $ を $ 2 $ 回行うことで $ s $ は`0011`となり、$ T $ と一致します。 このような手順で操作を行うと、$ 1+1+2+1+1\ =\ 6 $ 円が必要であり、これが必要な資金の最小値です。 このケースは部分点の制約を満たします。