外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

F - Trill or Jack or Switch

作成者 sevenc_nanashi

テスター unbakedbread

配点 400 点

実行時間制限
2 秒
メモリ制限
512 MiB

問題文

レーテーさんは譜面を研究しています。

譜面には、ノートが配置されるレーンが44本あり、時刻11から時刻NNまでの間にフロアノートが配置されます。
また、レーンは左から順にレーン11、レーン22、レーン33、レーン44と名付けられています。

時刻iiのフロアノートの配置は44文字の文字列SiS_iで表されます。
文字列SiS_iのjj文字目がoであれば、レーンjjにフロアノートが配置されていることを意味し、.であれば配置されていないことを意味します。
ただし、同じ時刻で3つ以上のフロアノートが配置されることはありません。

レーテーさんは左手・右手の人差し指でこの譜面を遊ぶことにしました。プレイは以下のように進行します:

  • 時刻00で、左手の人差し指をレーン11に、右手の人差し指をレーン44に置きます。
  • 時刻11から時刻NNまで、以下の操作を行います:
    • 時刻ttのノートをそれぞれ左手の人差し指で押すか、右手の人差し指で押すかを選択します。
      • このとき、一つの指で複数のノートを押すことはできません。
    • まず、人差し指を押すノートのレーンまで移動させます。レーンjjからレーンkkに移動させると、∣j−k∣×A|j - k| \times Aのコストがかかります。
      • 両方の指を同じレーンにおいたり、右手の指を左手の指よりも左のレーンに置いたりすることもできます。
    • ノートを叩きます。ノート1つにつきBBのコストがかかります。
    • もし、時刻t−1t-1でも同じ指でノートを押していた場合、それぞれ追加でCCのコストがそれぞれかかります。

全てのノートを押すための最小コストを求めてください。

制約

  • NN、AA、BB、CCは整数。
  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤A,B,C≤1091 \leq A, B, C \leq 10^9
  • SiS_iはoと.からなる長さ44の文字列である。
  • SiS_iに含まれるoの数は00以上22以下である。

入力

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

NABCN \quad A \quad B \quad C S1S_1 S2S_2 ⋮\vdots SNS_N

出力

最小のコストを出力してください。

サンプル 1

入力

4 2 3 10
o...
o...
o...
o...

出力

18

例えば、時刻11と33のノートを左手で、時刻22と44のノートを右手で押すことができます。

このとき、それぞれ以下のようにコストがかかります。

  • 時刻11:左手を移動させるコストは00、ノートを叩くコストは33、追加コストは00。
  • 時刻22:右手を移動させるコストは2×3=62 \times 3 = 6、ノートを叩くコストは33、追加コストは00。
  • 時刻33:左手を移動させるコストは00、ノートを叩くコストは33、追加コストは00。
  • 時刻44:右手を移動させるコストは00、ノートを叩くコストは33、追加コストは00。

コストの合計は1818となります。 1818未満のコストで全てのノートを押すことはできないため、答えは1818です。

なお、時刻22と44のノートを左手で、時刻11と33のノートを右手で押しても同じコストになります。

サンプル 2

入力

7 2 3 5
o.o.
.o..
.o..
o.o.
.o..
.o..
o.o.

出力

68

例えば、以下のようにノートを押すことができます。(ここで、Lは左手で押すことを、Rは右手で押すことを意味します。)

L.R.
.L..
.R..
L.R.
.L..
.R..
L.R.

このとき、移動コストは2×9=182 \times 9 = 18、ノートを叩くコストは3×10=303 \times 10 = 30かかります。また、時刻22、44、55、77はそれぞれ追加で55のコストがかかるため、合計で18+30+20=6818 + 30 + 20 = 68となります。

サンプル 3

入力

3 1 1 1
....
....
....

出力

0

ノートが降って来ない場合もあります。

サンプル 4

入力

4 1000000000 1000000000 1000000000
o..o
....
.oo.
o..o

出力

12000000000

移動コストは1000000000×4=40000000001000000000 \times 4 = 4000000000、ノートを叩くコストは1000000000×6=60000000001000000000 \times 6 = 6000000000、追加コストは1000000000×2=20000000001000000000 \times 2 = 2000000000かかるため、合計で4000000000+6000000000+2000000000=120000000004000000000 + 6000000000 + 2000000000 = 12000000000となります。

答えが32bit整数に収まらない場合があることに注意してください。
また、追加コストはレーンを問わず同じ指でノートを押した場合にかかることに注意してください。

参加受付は終了しました。