题目描述

有 $N$ 盏灯排成一横排，从左到右依次编号为 $1$ 到 $N$。每盏灯的颜色为红、绿、蓝三者之一。灯的颜色由字符串 $S$ 表示：当 $S$ 的第 $i$ 个字符（$1 \le i \le N$）为 R 时，灯 $i$ 的颜色为红色；为 G 时为绿色；为 B 时为蓝色。起初所有灯均处于点亮状态。

只要还有至少 $1$ 盏点亮的灯，JOI 君就可以按任意顺序执行以下 $3$ 种操作任意多次（也可以 $0$ 次）：

• 支付 $A$ 日元，将当前点亮的灯中最左边的一盏熄灭。
• 支付 $B$ 日元，将当前点亮的灯中最右边的一盏熄灭。
• 支付 $C$ 日元，选择 $1$ 盏当前点亮的灯，将其重新点亮为任意颜色。

JOI 君希望从远处看这排灯时呈现美丽的白色。为此，点亮的灯从左往右看的颜色序列必须形如 RGBRGB...RGB，即 RGB（红绿蓝）的重复。注意，如果存在 $0$ 盏点亮的灯（即所有灯均熄灭），也视为 RGB 的重复。注意像 GBRGBR 或 RGBRG 这样的颜色序列不满足条件。

给定灯的信息以及各项操作所需的金额，请编写程序求出使点亮的灯的颜色序列成为 RGB 的重复所需的最小金额。

数据范围

• $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$ 分）无额外限制。

输入格式

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

输出格式

在一行内输出使点亮的灯的颜色序列成为 RGB 的重复所需的最小金额，省略单位（日元），占 $1$ 行。

样例

6
GRBBRG
3 4 5

16

例如按如下方式进行 $4$ 次操作后，点亮的灯的颜色序列将变为 RGB 的重复。熄灭的灯用 - 表示。

1. 支付 $3$ 日元，将点亮的灯中最左边的灯 $1$ 熄灭。各盏灯的状态由字符串 -RBBRG 表示。
2. 支付 $4$ 日元，将点亮的灯中最右边的灯 $6$ 熄灭。各盏灯的状态由字符串 -RBBR- 表示。
3. 支付 $4$ 日元，将点亮的灯中最右边的灯 $5$ 熄灭。各盏灯的状态由字符串 -RBB-- 表示。
4. 支付 $5$ 日元，选择灯 $3$ 并将其重新点亮为绿色。各盏灯的状态由字符串 -RGB-- 表示。

因为无法支付少于 $16$ 日元使点亮的灯的颜色序列成为 RGB 的重复，所以输出 $16$。

该样例满足子任务 $2, 3, 6$ 的限制。

3
BRG
1000000000 1000000000 1

3

例如按如下方式进行 $3$ 次操作后，点亮的灯的颜色序列将变为 RGB 的重复。熄灭的灯用 - 表示。

1. 支付 $1$ 日元，选择灯 $2$ 并将其重新点亮为绿色。各盏灯的状态由字符串 BGG 表示。
2. 支付 $1$ 日元，选择灯 $3$ 并将其重新点亮为蓝色。各盏灯的状态由字符串 BGB 表示。
3. 支付 $1$ 日元，选择灯 $1$ 并将其重新点亮为红色。各盏灯的状态由字符串 RGB 表示。

因为无法支付少于 $3$ 日元使点亮的灯的颜色序列成为 RGB 的重复，所以输出 $3$。

该样例满足子任务 $1, 2, 3, 4, 5, 6$ 的限制。

3
GRB
9 11 14

27

例如按如下方式进行 $3$ 次操作后，点亮的灯的颜色序列将变为 RGB 的重复。熄灭的灯用 - 表示。

1. 支付 $9$ 日元，将点亮的灯中最左边的灯 $1$ 熄灭。各盏灯的状态由字符串 -RB 表示。
2. 支付 $9$ 日元，将点亮的灯中最左边的灯 $2$ 熄灭。各盏灯的状态由字符串 --B 表示。
3. 支付 $9$ 日元，将点亮的灯中最左边的灯 $3$ 熄灭。各盏灯的状态由字符串 --- 表示。

因为无法支付少于 $27$ 日元使点亮的灯的颜色序列成为 RGB 的重复，所以输出 $27$。注意存在 $0$ 盏点亮的灯的情况也视为满足条件。

该样例满足子任务 $1, 2, 3, 6$ 的限制。

9
RGBRGBRGB
1000000000 1000000000 1

0

因为灯的颜色序列已经是 RGB 的重复，所以输出 $0$。

该样例满足子任务 $2, 3, 4, 5, 6$ 的限制。

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

该样例满足子任务 $2, 3, 5, 6$ 的限制。

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

该样例满足子任务 $2, 3, 6$ 的限制。