#11202. White Light 2

White Light 2

问题描述

JOI 商店的灯以水平排列,从左到右编号为 1 到 N。每盏灯可以是红色、绿色或蓝色。灯的颜色由字符串表示,当字符为 R 时,灯为红色,当字符为 G 时,灯为绿色,当字符为 B 时,灯为蓝色。

只要有至少一盏灯亮着,JOI 可以按任意顺序执行以下操作任意次数:

  1. 支付 A 日元关闭最左边的一盏灯。
  2. 支付 B 日元关闭最右边的一盏灯。
  3. 支付 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