문제 설명

$N$개의 조명이 가로로 한 줄로 나열되어 있으며, 왼쪽부터 순서대로 $1$부터 $N$까지의 번호가 매겨져 있다. 각 조명의 색은 빨간색, 초록색, 파란색 중 하나이다. 조명의 색은 문자열 $S$로 나타내며, 조명 $i$ ($1 \le i \le N$)의 색은 $S$의 $i$번째 문자가 R일 때 빨간색, G일 때 초록색, B일 때 파란색이다. 처음에는 모든 조명이 켜져 있다.

JOI 군은 켜져 있는 조명이 $1$개 이상 있는 한, 다음 $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$의 제약 조건을 만족한다.