白色光 2 (White Light 2)

N 個のライトが横一列に並んでおり,左から順に 1 から N までの番号が付けられている.それぞれのライトの色は赤,緑,青のいずれかである.ライトの色は文字列 S によって表され,ライト i ( 1 ≦ i ≦ N ) の色は, S の i 文字目が R のとき赤, G のとき緑, B のとき青である.最初すべてのライトは点灯している.

JOI 君は点灯しているライトが 1 つ以上ある限り,以下の 3 種類の操作を好きな順番で好きな回数行うことができる.操作を 1 回も行わなくても構わない.

A 円を払って点灯しているライトの中で最も左にあるものを消灯する.

B 円を払って点灯しているライトの中で最も右にあるものを消灯する.

C 円を払って点灯しているライトを 1 つ選び,好きな色へ点灯し直す.

JOI 君は,遠くからこのライトの列を見たときにきれいな白色に見えるようにしたい.そのためには,点灯しているライトを左から見たときの色の並びが RGBRGB...RGB のように RGB (赤緑青)の繰り返しになっている必要がある.ただし, 1 つも点灯しているライトが存在しない場合も RGB の繰り返しであるとみなす. GBRGBR や RGBRG などの色の並びは条件を満たさないことに注意せよ.

ライトと操作に必要な金額の情報が与えられたとき,点灯しているライトの色の並びを RGB の繰り返しにするために必要な金額の最小値を求めるプログラムを作成せよ.

1 ≦ N ≦ 200 000 .

S は長さ N の文字列である.

S の各文字は R , G , B のいずれかである.

1 ≦ A ≦ 10 9 .

1 ≦ B ≦ 10 9 .

1 ≦ C ≦ 10 9 .

N, A, B, C は整数である.

( 4 点) N = 3 .

( 22 点) N ≦ 300 .

( 19 点) N ≦ 10 000 .

( 9 点) N は 3 の倍数, A = 10 9 , B = 10 9 , C = 1 .

( 10 点) A = 10 9 , B = 10 9 , C = 1 .

( 36 点) 追加の制約はない.

入力は以下の形式で与えられる.

N

S

A B C

点灯しているライトの色の並びを RGB の繰り返しにするために必要な金額の最小値を,単位 (円) を省いて 1 行で出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2024 Preliminary 2