P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2

有 $N$ 个灯横向排成一列，从左到右依次编号为 $1$ 到 $N$。每个灯的颜色为红、绿、蓝中的一种。灯的颜色由字符串 $S$ 表示：灯 $i$（$1 \le i \le N$）的颜色为，当 $S$ 的第 $i$ 个字符为 R 时是红色，为 G 时是绿色，为 B 时是蓝色。最初所有灯均为点亮状态。 只要点亮的灯至少有一个，JOI 君就可以按任意顺序、任意次数执行以下三种操作（也可以一次都不执行）： - 支付 $A$ 日元，熄灭当前所有点亮的灯中最左侧的一个。 - 支付 $B$ 日元，熄灭当前所有点亮的灯中最右侧的一个。 - 支付 $C$ 日元，任选一个当前点亮的灯，将其颜色更改为任意一种颜色。 JOI 君希望从远处看这排灯时，能呈现出漂亮的白色。为此，需要点亮的灯从左到右的颜色序列形如 RGBRGB…RGB，即按 RGB（红绿蓝）循环重复。注意，即使没有点亮的灯存在，也视为满足 RGB 循环重复的条件。例如，GBRGBR 或 RGBRG 等颜色序列不满足条件。 给定灯的颜色信息与操作所需金额，编写一个程序，求出将点亮灯的颜色序列调整为 RGB 循环重复所需的最小花费。

输入以如下格式给出： $N$ $S$ $A\ B\ C$

输出一行，表示将点亮灯的颜色序列调整为 RGB 循环重复所需的最小花费，单位“日元”省略不写。

### 样例 1 解释 例如，执行以下 4 次操作后，点亮灯的颜色序列可变为 RGB 循环重复。用 `-` 表示熄灭的灯。 - 支付 3 日元，熄灭当前点亮灯中最左侧的灯 1。此时各灯状态用字符串 `-RBBRG` 表示。 - 支付 4 日元，熄灭当前点亮灯中最右侧的灯 6。此时各灯状态用字符串 `-RBBR-` 表示。 - 支付 4 日元，熄灭当前点亮灯中最右侧的灯 5。此时各灯状态用字符串 `-RBB--` 表示。 - 支付 5 日元，选择灯 3，将其重新点亮为绿色。此时各灯状态用字符串 `-RGB--` 表示。 无法以低于 16 日元的花费使点亮灯的颜色序列变为 RGB 循环重复，因此输出 16。 该输入样例满足子任务 2、3、6 的约束。 ### 样例 2 解释 例如，执行以下 3 次操作后，点亮灯的颜色序列可变为 RGB 循环重复。用 `-` 表示熄灭的灯。 - 支付 1 日元，选择灯 2，将其重新点亮为绿色。此时各灯状态用字符串 `BGG` 表示。 - 支付 1 日元，选择灯 3，将其重新点亮为蓝色。此时各灯状态用字符串 `BGB` 表示。 - 支付 1 日元，选择灯 1，将其重新点亮为红色。此时各灯状态用字符串 `RGB` 表示。 无法以低于 3 日元的花费使点亮灯的颜色序列变为 RGB 循环重复，因此输出 3。 该输入样例满足子任务 1、2、3、4、5、6 的约束。 ### 样例 3 解释 例如，执行以下 3 次操作后，点亮灯的颜色序列可变为 RGB 循环重复。用 `-` 表示熄灭的灯。 - 支付 9 日元，熄灭当前点亮灯中最左侧的灯 1。此时各灯状态用字符串 `-RB` 表示。 - 支付 9 日元，熄灭当前点亮灯中最左侧的灯 2。此时各灯状态用字符串 `--B` 表示。 - 支付 9 日元，熄灭当前点亮灯中最左侧的灯 3。此时各灯状态用字符串 `---` 表示。 无法以低于 27 日元的花费使点亮灯的颜色序列变为 RGB 循环重复，因此输出 27。请注意，即使没有点亮的灯存在，也视为满足条件。 该输入样例满足子任务 1、2、3、6 的约束。 ### 样例 4 解释 当前灯的颜色序列已为 RGB 循环重复，因此输出 0。 该输入样例满足子任务 2、3、4、5、6 的约束。 ### 约束 - $1 \le N \le 200\,000$。 - $S$ 是长度为 $N$ 的字符串。 - $S$ 中的每个字符为 R、G、B 中的某一个。 - $1 \le A \le 10^9$。 - $1 \le B \le 10^9$。 - $1 \le C \le 10^9$。 - $N$、$A$、$B$、$C$ 均为整数。 ### 子任务 1. （4 分）$N = 3$。 2. （22 分）$N \le 300$。 3. （19 分）$N \le 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 分）无额外约束。 翻译由 Qwen3-235B 完成。