问题描述

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