White Light 2

Problem Statement

There are N lights arranged in a single row, numbered from 1 to N from left to right. The color of each light is one of red, green, or blue. The colors of the lights are represented by the string S, where the color of light i (1 ≦ i ≦ N) is red if the i-th character of S is R, green if it is G, and blue if it is B. Initially, all lights are turned on.

As long as at least one light is turned on, JOI-kun can perform the following three types of operations any number of times in any order. It is also possible to perform no operations at all.

• Pay A yen to turn off the leftmost light that is currently turned on.
• Pay B yen to turn off the rightmost light that is currently turned on.
• Pay C yen to choose one light that is currently turned on and change its color to any desired color.

JOI-kun wants the row of lights to appear as a beautiful white color when viewed from a distance. To achieve this, the sequence of colors of the lights that are turned on, read from left to right, must be a repetition of RGB (red, green, blue), such as RGBRGB...RGB. Note that the case where no lights are turned on is also considered to satisfy this condition. Be careful that color sequences such as GBRGBR or RGBRG do not satisfy the condition.

Given the information about the lights and the costs of the operations, write a program that finds the minimum amount of money required to make the sequence of colors of the lights that are turned on a repetition of RGB.

Constraints

• 1 ≦ N ≦ 200 000.
• S is a string of length N.
• Each character of S is one of R, G, or B.
• 1 ≦ A ≦ 10⁹.
• 1 ≦ B ≦ 10⁹.
• 1 ≦ C ≦ 10⁹.
• N, A, B, C are integers.

Input

The input is given in the following format.
N
S
A   B   C

Output

Output the minimum amount of money required to make the sequence of colors of the lights that are turned on a repetition of RGB, omitting the unit (yen), in one line.

Sample Input and Output

Sample Input 1

6
GRBBRG
3 4 5

Sample Output 1

16

For example, if the following 4 operations are performed, the sequence of colors of the lights that are turned on becomes a repetition of RGB. Lights that are turned off are represented by -.

1. Pay 3 yen to turn off light 1, which is the leftmost light that is currently turned on. The state of the lights is represented by the string -RBBRG.
2. Pay 4 yen to turn off light 6, which is the rightmost light that is currently turned on. The state of the lights is represented by the string -RBBR-.
3. Pay 4 yen to turn off light 5, which is the rightmost light that is currently turned on. The state of the lights is represented by the string -RBB--.
4. Pay 5 yen to choose light 3 and change its color to green. The state of the lights is represented by the string -RGB--.

It is not possible to make the sequence of colors of the lights that are turned on a repetition of RGB by paying less than 16 yen, so output 16.

Sample Input 2

3
BRG
1000000000 1000000000 1

Sample Output 2

3

For example, if the following 3 operations are performed, the sequence of colors of the lights that are turned on becomes a repetition of RGB. Lights that are turned off are represented by -.

1. Pay 1 yen to choose light 2 and change its color to green. The state of the lights is represented by the string BGG.
2. Pay 1 yen to choose light 3 and change its color to blue. The state of the lights is represented by the string BGB.
3. Pay 1 yen to choose light 1 and change its color to red. The state of the lights is represented by the string RGB.

It is not possible to make the sequence of colors of the lights that are turned on a repetition of RGB by paying less than 3 yen, so output 3.

Sample Input 3

3
GRB
9 11 14

Sample Output 3

27

For example, if the following 3 operations are performed, the sequence of colors of the lights that are turned on becomes a repetition of RGB. Lights that are turned off are represented by -.

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

It is not possible to make the sequence of colors of the lights that are turned on a repetition of RGB by paying less than 27 yen, so output 27. Note that the case where no lights are turned on also satisfies the condition.

Sample Input 4

9
RGBRGBRGB
1000000000 1000000000 1

Sample Output 4

0

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

Sample Input 5

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

Sample Output 5

2000000008

Sample Input 6

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

Sample Output 6

10107224827

---