#11202. White Light 2
White Light 2
问题描述
JOI 商店的灯以水平排列,从左到右编号为 1 到 N。每盏灯可以是红色、绿色或蓝色。灯的颜色由字符串表示,当字符为 R 时,灯为红色,当字符为 G 时,灯为绿色,当字符为 B 时,灯为蓝色。
只要有至少一盏灯亮着,JOI 可以按任意顺序执行以下操作任意次数:
- 支付 A 日元关闭最左边的一盏灯。
- 支付 B 日元关闭最右边的一盏灯。
- 支付 C 日元将任意一盏亮着的灯变为你喜欢的颜色。
JOI 希望当从远处看时,这排灯看起来是美丽的白色,即从左到右看时灯的颜色序列必须是 (红, 绿, 蓝) 的重复。注意,类似 RGBGBR 和 RRGBR 的颜色序列不满足条件。
给定灯的颜色信息和操作所需的金额,编写程序计算使亮着的灯的颜色序列重复 RGB 所需的最小金额。
约束条件
- 1 ≤ N ≤ 200,000
- S 是长度为 N 的字符串
- S 的每个字符为 R, G 或 B
- 1 ≤ A ≤ 10^9
- 1 ≤ B ≤ 10^9
- 1 ≤ C ≤ 10^9
- N, A, B, C 均为整数
输入
输入格式如下:
N
S
A B C
输出
输出使亮着的灯的颜色序列重复 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