問題文
レーテーさんは譜面を研究しています。
譜面には、ノートが配置されるレーンが本あり、時刻から時刻までの間にフロアノートが配置されます。
また、レーンは左から順にレーン、レーン、レーン、レーンと名付けられています。
時刻のフロアノートの配置は文字の文字列で表されます。
文字列の文字目がoであれば、レーンにフロアノートが配置されていることを意味し、.であれば配置されていないことを意味します。
ただし、同じ時刻で3つ以上のフロアノートが配置されることはありません。
レーテーさんは左手・右手の人差し指でこの譜面を遊ぶことにしました。プレイは以下のように進行します:
- 時刻で、左手の人差し指をレーンに、右手の人差し指をレーンに置きます。
- 時刻から時刻まで、以下の操作を行います:
- 時刻のノートをそれぞれ左手の人差し指で押すか、右手の人差し指で押すかを選択します。
- このとき、一つの指で複数のノートを押すことはできません。
- まず、人差し指を押すノートのレーンまで移動させます。レーンからレーンに移動させると、のコストがかかります。
- 両方の指を同じレーンにおいたり、右手の指を左手の指よりも左のレーンに置いたりすることもできます。
- ノートを叩きます。ノート1つにつきのコストがかかります。
- もし、時刻でも同じ指でノートを押していた場合、それぞれ追加でのコストがそれぞれかかります。
- 時刻のノートをそれぞれ左手の人差し指で押すか、右手の人差し指で押すかを選択します。
全てのノートを押すための最小コストを求めてください。
制約
- 、、、は整数。
- は
oと.からなる長さの文字列である。 - に含まれる
oの数は以上以下である。
入力
入力は以下の形式で標準入力から与えられます。
出力
最小のコストを出力してください。
サンプル 1
入力
4 2 3 10
o...
o...
o...
o...
出力
18
例えば、時刻とのノートを左手で、時刻とのノートを右手で押すことができます。
このとき、それぞれ以下のようにコストがかかります。
- 時刻:左手を移動させるコストは、ノートを叩くコストは、追加コストは。
- 時刻:右手を移動させるコストは、ノートを叩くコストは、追加コストは。
- 時刻:左手を移動させるコストは、ノートを叩くコストは、追加コストは。
- 時刻:右手を移動させるコストは、ノートを叩くコストは、追加コストは。
コストの合計はとなります。 未満のコストで全てのノートを押すことはできないため、答えはです。
なお、時刻とのノートを左手で、時刻とのノートを右手で押しても同じコストになります。
サンプル 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.
このとき、移動コストは、ノートを叩くコストはかかります。また、時刻、、、はそれぞれ追加でのコストがかかるため、合計でとなります。
サンプル 3
入力
3 1 1 1
....
....
....
出力
0
ノートが降って来ない場合もあります。
サンプル 4
入力
4 1000000000 1000000000 1000000000
o..o
....
.oo.
o..o
出力
12000000000
移動コストは、ノートを叩くコストは、追加コストはかかるため、合計でとなります。
答えが32bit整数に収まらない場合があることに注意してください。
また、追加コストはレーンを問わず同じ指でノートを押した場合にかかることに注意してください。
参加受付は終了しました。
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする