White Light 2

Time limit1sMemory limit1024 MB

Summary

Given a row of N red, green, or blue lights, find the minimum cost to turn off lights from either end or recolor lights so the lit colors repeat RGB.

Level: Medium7 of 10
Topics: Dynamic programming, String, Greedy
Solved: No attempts yet

Problem

There are N lights in a row, numbered 1 to N from left to right. Each light is red, green, or blue. The colors are given by a string S: light i is red if the i-th character of S is R, green if it is G, and blue if it is B. At the start, all lights are on.

As long as at least one light is on, JOI can perform the following three operations in any order and any number of times. He may also perform no operations at all.

A: Pay A yen to turn off the leftmost lit light.
B: Pay B yen to turn off the rightmost lit light.
C: Pay C yen to choose one lit light and relight it in any color.

Seen from far away, the lights look white when the colors of the lit lights, read from left to right, form a repetition of RGB, such as RGBRGB...RGB. A state with no lit lights also counts as a repetition of RGB. Sequences such as GBRGBR or RGBRG do not satisfy this condition.

Given the lights and the cost of each operation, find the minimum total cost needed to make the colors of the lit lights a repetition of RGB.

Input

N
S
A B C

Output

Print the minimum total cost needed to make the colors of the lit lights a repetition of RGB, on one line, without the unit (yen).

Constraints

$1 \le N \le 200000$
S is a string of length N, and each character is R, G, or B.
$1 \le A, B, C \le 10^9$
N, A, B, and C are integers.

Examples5

Example 1
Input
```
6
GRBBRG
3 4 5
```
Expected output
```
16
```
Example 2
Input
```
3
BRG
1000000000 1000000000 1
```
Expected output
```
3
```
Example 3
Input
```
3
GRB
9 11 14
```
Expected output
```
27
```
Example 4
Input
```
9
RGBRGBRGB
1000000000 1000000000 1
```
Expected output
```
0
```

Example 5

Input

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

Expected output

2000000008