DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦

C - 01文字列


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 700

問題文

文字列 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}
  • T01のみからなる文字列
  • A, \, B, \, C はいずれも整数

部分点

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

入力

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

A B C
T

出力

答えを 1 行に出力せよ。


入力例 1

1 10 2
0011

出力例 1

6
  • はじめに操作 12 回行います。s00となります。
  • 次に操作 31 回行います。 s11となります。
  • 最後に操作 12 回行うことで s0011となり、T と一致します。

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

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


入力例 2

5 2 8
0000100111100101100101100000100

出力例 2

169

入力例 3

1000000000 1000000000 50
11011001001001

出力例 3

14000000200

Submit提出する