AT_joi2024_yo2_c.白色光 2 (White Light 2)

有 $N$ 个灯依次排列成一行，从左到右依次编号为 $1$ 到 $N$。每个灯的颜色可以是红色、绿色或蓝色。灯的颜色由字符串 $S$ 表示，第 $i$ 个灯的颜色由 $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 分）$N = 3$。
2.（22 分）$N \leq 300$。
3.（19 分）$N \leq 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 分）没有额外限制。

样例解释 1

例如如下顺序进行 $4$ 次操作后，点亮的灯颜色排列会成为 RGB 循环。用 - 表示已熄灭的灯。

1. 支付 $3$ 日元熄灭最左边的第 $1$ 号灯，状态为 -RBBRG。
2. 支付 $4$ 日元熄灭最右边的第 $6$ 号灯，状态为 -RBBR-。
3. 支付 $4$ 日元熄灭最右边的第 $5$ 号灯，状态为 -RBB--。
4. 支付 $5$ 日元把第 $3$ 号灯变成绿色，状态为 -RGB--。

无法少于 $16$ 日元实现目标，因此输出 $16$。

这个输入满足小子任务 $2,3,6$ 的约束。

样例解释 2

如下进行 $3$ 次操作后，点亮的灯颜色排列会成为 RGB 循环（-为熄灭）：

1. 支付 $1$ 日元把第 $2$ 号灯变为绿色，状态为 BGG。
2. 支付 $1$ 日元把第 $3$ 号灯变为蓝色，状态为 BGB。
3. 支付 $1$ 日元把第 $1$ 号灯变为红色，状态为 RGB。

无法少于 $3$ 日元实现，因此输出 $3$。

满足小子任务 $1,2,3,4,5,6$ 的约束。

样例解释 3

如下操作 $3$ 次，点亮的灯颜色排列会变为 RGB 循环（-表示熄灭）：

1. 支付 $9$ 日元熄灭最左边的第 $1$ 号灯，状态为 -RB。
2. 支付 $9$ 日元熄灭最左边的第 $2$ 号灯，状态为 --B。
3. 支付 $9$ 日元熄灭最左边的第 $3$ 号灯，状态为 ---。

无法少于 $27$ 日元实现，因此输出 $27$。注意，当没有任何灯亮着时也认为满足条件。

该输入满足小子任务 $1,2,3,6$。

样例解释 4

当前排列已经是 RGB 的循环，因此输出 $0$。

输入满足小子任务 $2,3,4,5,6$。

样例解释 5

输入满足小子任务 $2,3,5,6$。

样例解释 6

输入满足小子任务 $2,3,6$。

数据范围

• $1 \leq N \leq 200\,000$。
• $S$ 是长度为 $N$ 的字符串。
• $S$ 的每个字符是 R、G 或 B。
• $1 \leq A \leq 10^9$。
• $1 \leq B \leq 10^9$。
• $1 \leq C \leq 10^9$。
• $N, A, B, C$ 均为整数。

由 ChatGPT 5 翻译