题目描述

有 $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 循环重复所需的最小花费，单位“日元”省略不写。

6
GRBBRG
3 4 5

16

3
BRG
1000000000 1000000000 1

3

3
GRB
9 11 14

27

9
RGBRGBRGB
1000000000 1000000000 1

0

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

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

约束

• $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 完成。