백색광 2

문제

$N$ 개의 조명이 가로로 한 줄로 늘어서 있으며, 왼쪽부터 순서대로 $1$ 부터 $N$ 까지의 번호가 붙어 있다. 각 조명의 색은 빨강, 초록, 파랑 중 하나이다. 조명의 색은 문자열 $S$ 로 표현되며, 조명 $i$ ($1 \le i \le N$) 의 색은 $S$ 의 $i$ 번째 문자가 R 이면 빨강, G 이면 초록, B 이면 파랑이다. 처음에 모든 조명은 켜져 있다.

JOI 군은 켜져 있는 조명이 $1$ 개 이상 있는 한, 다음 $3$ 종류의 조작을 원하는 순서로 원하는 횟수만큼 할 수 있다. 조작을 $1$ 번도 하지 않아도 된다.

• $A$ 엔을 지불하고 켜져 있는 조명 중 가장 왼쪽에 있는 것을 끈다.
• $B$ 엔을 지불하고 켜져 있는 조명 중 가장 오른쪽에 있는 것을 끈다.
• $C$ 엔을 지불하고 켜져 있는 조명을 $1$ 개 골라, 원하는 색으로 다시 켠다.

JOI 군은 멀리서 이 조명의 줄을 보았을 때 깨끗한 백색으로 보이게 하고 싶다. 그러기 위해서는 켜져 있는 조명을 왼쪽부터 보았을 때의 색의 나열이 RGBRGB...RGB 와 같이 RGB(빨강 초록 파랑)의 반복이 되어야 한다. 다만, 켜져 있는 조명이 $1$ 개도 존재하지 않는 경우도 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$ 줄로 출력한다.

예제 입력 1

6
GRBBRG
3 4 5

예제 출력 1

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$ 의 제약을 만족한다.

예제 입력 2

3
BRG
1000000000 1000000000 1

예제 출력 2

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

3
GRB
9 11 14

예제 출력 3

27

예를 들어 다음과 같이 $3$ 번의 조작을 하면, 켜져 있는 조명의 색의 나열이 RGB 의 반복이 된다. 꺼져 있는 조명을 - 로 나타낸다.

1. $9$ 엔을 지불하고 켜져 있는 조명 중 가장 왼쪽에 있는 조명 $1$ 을 끈다. 각 조명의 상태는 문자열 -RB 로 표현된다.
2. $9$ 엔을 지불하고 켜져 있는 조명 중 가장 왼쪽에 있는 조명 $2$ 를 끈다. 각 조명의 상태는 문자열 --B 로 표현된다.
3. $9$ 엔을 지불하고 켜져 있는 조명 중 가장 왼쪽에 있는 조명 $3$ 을 끈다. 각 조명의 상태는 문자열 --- 로 표현된다.

$27$ 엔 미만의 금액을 지불하여 켜져 있는 조명의 색의 나열을 RGB 의 반복으로 만들 수는 없으므로, $27$ 을 출력한다. 켜져 있는 조명이 $1$ 개도 존재하지 않는 경우도 조건을 만족하는 것으로 함에 주의하시오.

이 예제는 서브태스크 $1,2,3,6$ 의 제약을 만족한다.

예제 입력 4

9
RGBRGBRGB
1000000000 1000000000 1

예제 출력 4

0

이미 조명의 색의 나열이 RGB 의 반복으로 되어 있으므로, $0$ 을 출력한다.

이 예제는 서브태스크 $2,3,4,5,6$ 의 제약을 만족한다.

예제 입력 5

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

예제 출력 5

2000000008

이 예제는 서브태스크 $2,3,5,6$ 의 제약을 만족한다.

예제 입력 6

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

예제 출력 6

10107224827

이 예제는 서브태스크 $2,3,6$ 의 제약을 만족한다.