AT_joi2024_yo2_c 白色光 2 (White Light 2)

$ N $ 個のライトが横一列に並んでおり，左から順に $ 1 $ から $ N $ までの番号が付けられている．それぞれのライトの色は赤，緑，青のいずれかである．ライトの色は文字列 $ S $ によって表され，ライト $ i $ ( $ 1 \leqq i \leqq N $ ) の色は， $ S $ の $ i $ 文字目が `R` のとき赤，`G` のとき緑，`B` のとき青である．最初すべてのライトは点灯している． JOI 君は点灯しているライトが $ 1 $ つ以上ある限り，以下の $ 3 $ 種類の操作を好きな順番で好きな回数行うことができる．操作を $ 1 $ 回も行わなくても構わない． - $ A $ 円を払って点灯しているライトの中で最も左にあるものを消灯する． - $ B $ 円を払って点灯しているライトの中で最も右にあるものを消灯する． - $ C $ 円を払って点灯しているライトを $ 1 $ つ選び，好きな色へ点灯し直す． JOI 君は，遠くからこのライトの列を見たときにきれいな白色に見えるようにしたい．そのためには，点灯しているライトを左から見たときの色の並びが `RGBRGB...RGB` のように `RGB`（赤緑青）の繰り返しになっている必要がある．ただし， $ 1 $ つも点灯しているライトが存在しない場合も `RGB` の繰り返しであるとみなす． `GBRGBR` や `RGBRG` などの色の並びは条件を満たさないことに注意せよ． ライトと操作に必要な金額の情報が与えられたとき，点灯しているライトの色の並びを `RGB` の繰り返しにするために必要な金額の最小値を求めるプログラムを作成せよ．

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

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

### 小課題 1. ( $ 4 $ 点) $ N = 3 $ ． 2. ( $ 22 $ 点) $ N \leqq 300 $ ． 3. ( $ 19 $ 点) $ N \leqq 10\,000 $ ． 4. ( $ 9 $ 点) $ N $ は $ 3 $ の倍数， $ A = 10^9 $ ， $ B = 10^9 $ ， $ C = 1 $ ． 5. ( $ 10 $ 点) $ A = 10^9 $ ， $ B = 10^9 $ ， $ C = 1 $ ． 6. ( $ 36 $ 点) 追加の制約はない． ### Sample Explanation 1 例えば以下のように $ 4 $ 回の操作を行ったとき，点灯しているライトの色の並びが `RGB` の繰り返しになる．消灯しているライトを `-` で表す． 1. $ 3 $ 円を払って点灯しているライトのうち最も左にあるライト $ 1 $ を消灯させる．それぞれのライトの状態は文字列 `-RBBRG` で表される． 2. $ 4 $ 円を払って点灯しているライトのうち最も右にあるライト $ 6 $ を消灯させる．それぞれのライトの状態は文字列 `-RBBR-` で表される． 3. $ 4 $ 円を払って点灯しているライトのうち最も右にあるライト $ 5 $ を消灯させる．それぞれのライトの状態は文字列 `-RBB--` で表される． 4. $ 5 $ 円を払ってライト $ 3 $ を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列 `-RGB--` で表される． $ 16 $ 円未満の金額を払って点灯しているライトの色の並びを `RGB` の繰り返しにすることはできないため， $ 16 $ を出力する． この入力例は小課題 $ 2,3,6 $ の制約を満たす． ### Sample Explanation 2 例えば以下のように $ 3 $ 回の操作を行ったとき，点灯しているライトの色の並びが `RGB` の繰り返しになる．消灯しているライトを `-` で表す． 1. $ 1 $ 円を払ってライト $ 2 $ を選び，緑色へ点灯し直す．それぞれのライトの状態は文字列 `BGG` で表される． 2. $ 1 $ 円を払ってライト $ 3 $ を選び，青色へ点灯し直す．それぞれのライトの状態は文字列 `BGB` で表される． 3. $ 1 $ 円を払ってライト $ 1 $ を選び，赤色へ点灯し直す．それぞれのライトの状態は文字列 `RGB` で表される． $ 3 $ 円未満の金額を払って点灯しているライトの色の並びを `RGB` の繰り返しにすることはできないため， $ 3 $ を出力する． この入力例は小課題 $ 1,2,3,4,5,6 $ の制約を満たす． ### Sample Explanation 3 例えば以下のように $ 3 $ 回の操作を行ったとき，点灯しているライトの色の並びが `RGB` の繰り返しになる．消灯しているライトを `-` で表す． 1. $ 9 $ 円を払って点灯しているライトのうち最も左にあるライト $ 1 $ を消灯させる．それぞれのライトの状態は文字列 `-RB` で表される． 2. $ 9 $ 円を払って点灯しているライトのうち最も左にあるライト $ 2 $ を消灯させる．それぞれのライトの状態は文字列 `--B` で表される． 3. $ 9 $ 円を払って点灯しているライトのうち最も左にあるライト $ 3 $ を消灯させる．それぞれのライトの状態は文字列 `---` で表される． $ 27 $ 円未満の金額を払って点灯しているライトの色の並びを `RGB` の繰り返しにすることはできないため， $ 27 $ を出力する． $ 1 $ つも点灯しているライトが存在しない場合も条件を満たすものとすることに注意せよ． この入力例は小課題 $ 1,2,3,6 $ の制約を満たす． ### Sample Explanation 4 既にライトの色の並びは `RGB` の繰り返しになっているため， $ 0 $ を出力する． この入力例は小課題 $ 2,3,4,5,6 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 2,3,5,6 $ の制約を満たす． ### Sample Explanation 6 この入力例は小課題 $ 2,3,6 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 200\,000 $ ． - $ S $ は長さ $ N $ の文字列である． - $ S $ の各文字は `R`，`G`，`B` のいずれかである． - $ 1 \leqq A \leqq 10^9 $ ． - $ 1 \leqq B \leqq 10^9 $ ． - $ 1 \leqq C \leqq 10^9 $ ． - $ N, A, B, C $ は整数である．