#214409. [JOI2024 预选赛 R2] 白色灯 2 / White Light 2

有 个灯横向排成一列，从左到右依次编号为 到 。每个灯的颜色为红、绿、蓝中的一种。灯的颜色由字符串 表示：灯 （）的颜色为，当 的第 个字符为 R 时是红色，为 G 时是绿色，为 B 时是蓝色。最初所有灯均为点亮状态。

只要点亮的灯至少有一个，JOI 君就可以按任意顺序、任意次数执行以下三种操作（也可以一次都不执行）：

• 支付 日元，熄灭当前所有点亮的灯中最左侧的一个。
• 支付 日元，熄灭当前所有点亮的灯中最右侧的一个。
• 支付 日元，任选一个当前点亮的灯，将其颜色更改为任意一种颜色。

JOI 君希望从远处看这排灯时，能呈现出漂亮的白色。为此，需要点亮的灯从左到右的颜色序列形如 RGBRGB…RGB，即按 RGB（红绿蓝）循环重复。注意，即使没有点亮的灯存在，也视为满足 RGB 循环重复的条件。例如，GBRGBR 或 RGBRG 等颜色序列不满足条件。

给定灯的颜色信息与操作所需金额，编写一个程序，求出将点亮灯的颜色序列调整为 RGB 循环重复所需的最小花费。

输入以如下格式给出：

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

样例输入 1

6
GRBBRG
3 4 5

样例输出 1

16

样例输入 2

3
BRG
1000000000 1000000000 1

样例输出 2

3

样例输入 3

3
GRB
9 11 14

样例输出 3

27

样例输入 4

9
RGBRGBRGB
1000000000 1000000000 1

样例输出 4

0

样例输入 5

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

样例输出 5

2000000008

样例输入 6

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

样例输出 6

10107224827

样例 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 的约束。

约束

• 。
• 是长度为 的字符串。
• 中的每个字符为 R、G、B 中的某一个。
• 。
• 。
• 。
• 、、、 均为整数。

子任务

1. （4 分）。
2. （22 分）。
3. （19 分）。
4. （9 分） 是 3 的倍数，，，。
5. （10 分），，。
6. （36 分）无额外约束。

翻译由 Qwen3-235B 完成。