問題文

文字列 $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$ 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

$A$ $B$ $C$ $T$

出力

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

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