問題文

文字列 s に対して以下の 3 種類の操作を何度か行い、文字列 T を作ることを考えます。 s ははじめ空文字列です。

1. A 円払って s の先頭に0を挿入する。
2. B 円払って s の末尾に1を挿入する。
3. C 円払って s に含まれる0を全て1に、s に含まれる1を全て0に置換する。

文字列 T を作るために必要な資金の最小値を求めてください。

制約

• 1 ≦ A, \, B, \, C ≦ 10^{9}
• 1 ≦ |T| ≦ 2 \times 10^{5}
• T は0と1のみからなる文字列
• A, \, B, \, C はいずれも整数

部分点

• 1≦|T|≦10 を満たすデータセットに正解した場合は、300 点が与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 400 点が与えられる。

入力例 1

1 10 2
0011

出力例 1

6

• はじめに操作 1 を 2 回行います。s は00となります。
• 次に操作 3 を 1 回行います。 s は11となります。
• 最後に操作 1 を 2 回行うことで s は0011となり、T と一致します。

このような手順で操作を行うと、1+1+2+1+1 = 6 円が必要であり、これが必要な資金の最小値です。

このケースは部分点の制約を満たします。

入力例 2

5 2 8
0000100111100101100101100000100

出力例 2

169

入力例 3

1000000000 1000000000 50
11011001001001

出力例 3

14000000200