题目描述

小泽面前有 $n$ 盏从左到右排列的灯。开始时所有灯都处于点亮状态，每盏灯的颜色是红、绿、蓝三种颜色之一。用字符 R、G、B 分别表示红灯、绿灯和蓝灯，字符串 $S$ 按从左到右的顺序记录了所有灯的初始颜色。

小泽可以执行下面三种操作，次数不限：

1. 熄灭当前仍亮着的最左端灯，花费 $A$；
2. 熄灭当前仍亮着的最右端灯，花费 $B$；
3. 选择任意一盏仍亮着的灯，把它改成另外两种颜色中的任意一种，花费 $C$。改色后这盏灯仍然亮着。

当所有仍亮着的灯满足下列条件时，它们能够合成完美的白光：

• 亮灯数量是 $3$ 的倍数；
• 从左到右的颜色依次为 R、G、B，并按这一顺序不断重复。

例如，RGBRGBRGB 能够合成完美白光；RGBRG 的灯数不是 $3$ 的倍数，GBRGBR 又没有从 R 开始，所以二者都不符合要求。亮灯数为 $0$ 时也视为满足条件，也就是说，小泽可以选择把全部灯熄灭。

请计算小泽至少需要花费多少，才能让剩余的灯合成完美白光。

输入格式

第一行输入一个整数 $n$，表示灯的数量。

第二行输入一个长度为 $n$ 的字符串 $S$。字符串只包含 R、G、B。

第三行输入三个整数 $A,B,C$，分别表示熄灭最左端灯、熄灭最右端灯和改变一盏灯颜色的费用。

输出格式

输出一行一个整数，表示达到要求的最小总花费。

输入输出样例 #1

6
GRRGBG
3 4 5

10

输入输出样例 #2

3
RGB
9 11 14

0

输入输出样例 #3

10
BGGBGGBGGB
1000000000 1000000000 1

1000000003

输入输出样例 #4

23
RRRRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

边界测试 #1

1
R
100 1 100

1

边界测试 #2

3
BBB
10 10 1

2

样例说明

样例 #1 中，可以熄灭左端两盏灯和右端一盏灯，灯的状态变为 --RGB-。剩下的三盏灯依次是 R、G、B，总费用为 $2A+B=10$。

样例 #2 中，初始灯串已经是 RGB，无需执行任何操作，花费为 $0$。

样例 #3 中，可以先熄灭最左端的一盏灯，再改变原编号为 $2,5,8$ 的三盏灯的颜色，最终得到 -RGBRGBRGB。总费用为 $10^9+3$。

边界测试 #1 只有一盏灯，不可能保留非空的合法灯串，因此选择从费用更低的右端将它熄灭。边界测试 #2 恰有三盏灯，修改两盏灯的颜色比全部熄灭更便宜。

测试点限制

测试点编号	$n$	特殊性质
$1\sim2$	$=3$	无
$3\sim8$	$\le 300$
$9\sim12$	$\le 5000$
$13\sim14$	$\le 2\times10^5$	$A=B=10^9,\ C=1$
$15\sim20$		无

对于所有测试数据：

$$1\le n\le 2\times 10^5,\qquad 1\le A,B,C\le 10^9,\qquad |S|=n.$$

字符串 $S$ 中只会出现 R、G、B。