Problem Statement

There are $N$ lights arranged in a horizontal row, numbered from $1$ to $N$ from left to right. The color of each light is red, green, or blue. The colors of the lights are represented by a string $S$, where the color of light $i$ ($1 \le i \le N$) is red when the $i$-th character of $S$ is R, green when it is G, and blue when it is B. Initially, all lights are lit.

As long as there is at least $1$ lit light, JOI-kun can perform the following $3$ types of operations in any order any number of times. It is also allowed to perform $0$ operations.

• Pay $A$ yen to turn off the leftmost lit light among the currently lit lights.
• Pay $B$ yen to turn off the rightmost lit light among the currently lit lights.
• Pay $C$ yen to choose $1$ currently lit light and re-light it to any color he likes.

JOI-kun wants this row of lights to look like a beautiful white color when viewed from afar. For that, the sequence of colors of the lit lights when viewed from left to right must be a repetition of RGB (red, green, blue) like RGBRGB...RGB. Note that the case where there are $0$ lit lights is also regarded as a repetition of RGB. Note that color sequences such as GBRGBR or RGBRG do not satisfy the condition.

Given the information about the lights and the costs required for the operations, write a program to find the minimum amount of money required to make the color sequence of the lit lights a repetition of RGB.

Constraints

• $1 \le N \le 200\,000$.
• $S$ is a string of length $N$.
• Each character of $S$ is R, G, or B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ are integers.

Subtasks

1. ($4$ points) $N = 3$.
2. ($22$ points) $N \le 300$.
3. ($19$ points) $N \le 10\,000$.
4. ($9$ points) $N$ is a multiple of $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ points) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ points) No additional constraints.

Input

Input is given in the following format: $N$ $S$ $A \ B \ C$

Output

Output the minimum amount of money required to make the color sequence of the lit lights a repetition of RGB on $1$ line, omitting the unit (yen).

Sample Input and Output

6
GRBBRG
3 4 5

16

For example, when $4$ operations are performed as follows, the color sequence of the lit lights becomes a repetition of RGB. A turned-off light is represented by -.

1. Pay $3$ yen to turn off light $1$, which is the leftmost lit light. The state of the lights is represented by the string -RBBRG.
2. Pay $4$ yen to turn off light $6$, which is the rightmost lit light. The state of the lights is represented by the string -RBBR-.
3. Pay $4$ yen to turn off light $5$, which is the rightmost lit light. The state of the lights is represented by the string -RBB--.
4. Pay $5$ yen to choose light $3$ and re-light it to green. The state of the lights is represented by the string -RGB--.

Since it is impossible to make the color sequence of the lit lights a repetition of RGB by paying less than $16$ yen, output $16$.

This sample input satisfies the constraints of Subtasks $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

For example, when $3$ operations are performed as follows, the color sequence of the lit lights becomes a repetition of RGB. A turned-off light is represented by -.

1. Pay $1$ yen to choose light $2$ and re-light it to green. The state of the lights is represented by the string BGG.
2. Pay $1$ yen to choose light $3$ and re-light it to blue. The state of the lights is represented by the string BGB.
3. Pay $1$ yen to choose light $1$ and re-light it to red. The state of the lights is represented by the string RGB.

Since it is impossible to make the color sequence of the lit lights a repetition of RGB by paying less than $3$ yen, output $3$.

This sample input satisfies the constraints of Subtasks $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

For example, when $3$ operations are performed as follows, the color sequence of the lit lights becomes a repetition of RGB. A turned-off light is represented by -.

1. Pay $9$ yen to turn off light $1$, which is the leftmost lit light. The state of the lights is represented by the string -RB.
2. Pay $9$ yen to turn off light $2$, which is the leftmost lit light. The state of the lights is represented by the string --B.
3. Pay $9$ yen to turn off light $3$, which is the leftmost lit light. The state of the lights is represented by the string ---.

Since it is impossible to make the color sequence of the lit lights a repetition of RGB by paying less than $27$ yen, output $27$. Note that the case where there are $0$ lit lights also satisfies the condition.

This sample input satisfies the constraints of Subtasks $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Since the color sequence of the lights is already a repetition of RGB, output $0$.

This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

This sample input satisfies the constraints of Subtasks $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

This sample input satisfies the constraints of Subtasks $2, 3, 6$.