Problembeskrivelse

Det står $N$ lamper på en horisontal rekke, nummerert fra $1$ til $N$ fra venstre til høyre. Fargen på hver lampe er rød, grønn eller blå. Lampenes farger representeres av en streng $S$, der fargen på lampe $i$ ($1 \le i \le N$) er rød når det $i$-te tegnet i $S$ er R, grønn når det er G og blå når det er B. Til å begynne med lyser alle lampene.

Så lenge det er minst $1$ lampe som lyser, kan JOI-kun utføre følgende $3$ typer operasjoner i hvilken som helst rekkefølge og så mange ganger han vil (det er også lov å utføre $0$ operasjoner):

• Betale $A$ yen for å slukke den lysende lampen lengst til venstre.
• Betale $B$ yen for å slukke den lysende lampen lengst til høyre.
• Betale $C$ yen for å velge $1$ lysende lampe og tenne den på nytt i valgfri farge.

JOI-kun ønsker at denne rekken med lamper skal se ut som et vakkert hvitt lys når man ser den på avstand. For at det skal skje, må fargerekken til de lysende lampene sett fra venstre til høyre være en gjentakelse av RGB (rød, grønn, blå) slik som RGBRGB...RGB. Merk at tilfellet der det er $0$ lysende lamper også regnes som en gjentakelse av RGB. Merk at fargerekker som GBRGBR eller RGBRG ikke oppfyller betingelsen.

Gitt informasjonen om lampene og kostnadene for operasjonene, skriv et program for å finne det minste pengebeløpet som kreves for å gjøre fargerekken til de lysende lampene til en gjentakelse av RGB.

Begrensninger

• $1 \le N \le 200\,000$.
• $S$ er en streng med lengde $N$.
• Hvert tegn i $S$ er R, G eller B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ er heltall.

Deloppgaver

1. ($4$ poeng) $N = 3$.
2. ($22$ poeng) $N \le 300$.
3. ($19$ poeng) $N \le 10\,000$.
4. ($9$ poeng) $N$ er et multiplum av $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ poeng) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ poeng) Ingen ytterligere begrensninger.

Inndata

Inndata gis i følgende format: $N$ $S$ $A \ B \ C$

Utdata

Skriv ut på $1$ linje det minste pengebeløpet som kreves for å gjøre fargerekken til de lysende lampene til en gjentakelse av RGB, uten enhet (yen).

Eksempler

6
GRBBRG
3 4 5

16

For eksempel, når $4$ operasjoner utføres som følger, blir fargerekken til de lysende lampene en gjentakelse av RGB. En slukket lampe representeres med -.

1. Betal $3$ yen for å slukke lampe $1$, som er den lysende lampen lengst til venstre. Tilstanden til lampene representeres av strengen -RBBRG.
2. Betal $4$ yen for å slukke lampe $6$, som er den lysende lampen lengst til høyre. Tilstanden til lampene representeres av strengen -RBBR-.
3. Betal $4$ yen for å slukke lampe $5$, som er den lysende lampen lengst til høyre. Tilstanden til lampene representeres av strengen -RBB--.
4. Betal $5$ yen for å velge lampe $3$ og tenne den på nytt i grønt. Tilstanden til lampene representeres av strengen -RGB--.

Siden det er umulig å gjøre fargerekken til en gjentakelse av RGB ved å betale mindre enn $16$ yen, skrives $16$ ut.

Dette eksempelet oppfyller begrensningene i deloppgave $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

For eksempel, når $3$ operasjoner utføres som følger, blir fargerekken til de lysende lampene en gjentakelse av RGB. En slukket lampe representeres med -.

1. Betal $1$ yen for å velge lampe $2$ og tenne den på nytt i grønt. Tilstanden til lampene representeres av strengen BGG.
2. Betal $1$ yen for å velge lampe $3$ og tenne den på nytt i blått. Tilstanden til lampene representeres av strengen BGB.
3. Betal $1$ yen for å velge lampe $1$ og tenne den på nytt i rødt. Tilstanden til lampene representeres av strengen RGB.

Siden det er umulig å gjøre fargerekken til en gjentakelse av RGB ved å betale mindre enn $3$ yen, skrives $3$ ut.

Dette eksempelet oppfyller begrensningene i deloppgave $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

For eksempel, når $3$ operasjoner utføres som følger, blir fargerekken til de lysende lampene en gjentakelse av RGB. En slukket lampe representeres med -.

1. Betal $9$ yen for å slukke lampe $1$, som er den lysende lampen lengst til venstre. Tilstanden til lampene representeres av strengen -RB.
2. Betal $9$ yen for å slukke lampe $2$, som er den lysende lampen lengst til venstre. Tilstanden til lampene representeres av strengen --B.
3. Betal $9$ yen for å slukke lampe $3$, som er den lysende lampen lengst til venstre. Tilstanden til lampene representeres av strengen ---.

Siden det er umulig å gjøre fargerekken til en gjentakelse av RGB ved å betale mindre enn $27$ yen, skrives $27$ ut. Merk at også tilfellet der det er $0$ lysende lamper oppfyller betingelsen.

Dette eksempelet oppfyller begrensningene i deloppgave $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Siden fargerekken til lampene allerede er en gjentakelse av RGB, skrives $0$ ut.

Dette eksempelet oppfyller begrensningene i deloppgave $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Dette eksempelet oppfyller begrensningene i deloppgave $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Dette eksempelet oppfyller begrensningene i deloppgave $2, 3, 6$.