第23回日本情報オリンピック　二次予選

2023年12月15日
情報オリンピック日本委員会

問題文

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⁹．
• 1 ≦ B ≦ 10⁹．
• 1 ≦ C ≦ 10⁹．
• N, A, B, C は整数である．

小課題

1. (4 点) N = 3．
2. (22 点) N ≦ 300．
3. (19 点) N ≦ 10 000．
4. (9 点) N は 3 の倍数，A = 10⁹，B = 10⁹，C = 1．
5. (10 点) A = 10⁹，B = 10⁹，C = 1．
6. (36 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
S
A   B   C

出力

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

入出力例

入力例 1
6
GRBBRG
3 4 5

出力例 1
16

例えば以下のように 4 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．

1. 3 円を払って点灯しているライトのうち最も左にあるライト 1 を消灯させる．それぞれのライトの状態は文字列 -RBBRG で表される．
2. 4 円を払って点灯しているライトのうち最も右にあるライト 6 を消灯させる．それぞれのライトの状態は文字列 -RBBR- で表される．
3. 4 円を払って点灯しているライトのうち最も右にあるライト 5 を消灯させる．それぞれのライトの状態は文字列 -RBB-- で表される．
4. 5 円を払ってライト 3 を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列 -RGB-- で表される．

16 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，16 を出力する．

この入力例は小課題 2,3,6 の制約を満たす．

入力例 2
3
BRG
1000000000 1000000000 1

出力例 2
3

例えば以下のように 3 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．

1. 1 円を払ってライト 2 を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列 BGG で表される．
2. 1 円を払ってライト 3 を選び，青色へ点灯し直す．それぞれのライトの状態は文字列 BGB で表される．
3. 1 円を払ってライト 1 を選び，赤色へ点灯し直す．それぞれのライトの状態は文字列 RGB で表される．

3 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，3 を出力する．

この入力例は小課題 1,2,3,4,5,6 の制約を満たす．

入力例 3
3
GRB
9 11 14

出力例 3
27

例えば以下のように 3 回の操作を行ったとき，点灯しているライトの色の並びが RGB の繰り返しになる．消灯しているライトを - で表す．

1. 9 円を払って点灯しているライトのうち最も左にあるライト 1 を消灯させる．それぞれのライトの状態は文字列 -RB で表される．
2. 9 円を払って点灯しているライトのうち最も左にあるライト 2 を消灯させる．それぞれのライトの状態は文字列 --B で表される．
3. 9 円を払って点灯しているライトのうち最も左にあるライト 3 を消灯させる．それぞれのライトの状態は文字列 --- で表される．

27 円未満の金額を払って点灯しているライトの色の並びを RGB の繰り返しにすることはできないため，27 を出力する．1 つも点灯しているライトが存在しない場合も条件を満たすものとすることに注意せよ．

この入力例は小課題 1,2,3,6 の制約を満たす．

入力例 4
9
RGBRGBRGB
1000000000 1000000000 1

出力例 4
0

既にライトの色の並びは RGB の繰り返しになっているため，0 を出力する．

この入力例は小課題 2,3,4,5,6 の制約を満たす．

入力例 5
20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

出力例 5
2000000008

この入力例は小課題 2,3,5,6 の制約を満たす．

入力例 6
23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

出力例 6
10107224827

この入力例は小課題 2,3,6 の制約を満たす．