Problembeskrivning

Det finns $N$ lampor placerade i en horisontell rad, numrerade från $1$ till $N$ från vänster till höger. Färgen på varje lampa är röd, grön eller blå. Lampornas färger representeras av en sträng $S$, där färgen på lampa $i$ ($1 \le i \le N$) är röd när det $i$-te tecknet i $S$ är R, grön när det är G och blå när det är B. Från början är alla lampor tända.

Så länge det finns minst $1$ tänd lampa kan JOI-kun utföra följande $3$ typer av operationer i valfri ordning hur många gånger som helst (det är också tillåtet att utföra $0$ operationer):

• Betala $A$ yen för att släcka den tända lampan längst till vänster.
• Betala $B$ yen för att släcka den tända lampan längst till höger.
• Betala $C$ yen för att välja $1$ tänd lampa och tända om den i valfri färg.

JOI-kun vill att denna rad av lampor ska se ut som ett vackert vitt ljus när man betraktar den på avstånd. För detta måste färgsekvensen för de tända lamporna från vänster till höger vara en upprepning av RGB (röd, grön, blå) såsom RGBRGB...RGB. Notera att även fallet där det finns $0$ tända lampor räknas som en upprepning av RGB. Observera att färgsekvenser som GBRGBR eller RGBRG inte uppfyller villkoret.

Givet informationen om lamporna och kostnaderna för operationerna, skriv ett program för att hitta den minsta summan pengar som krävs för att göra de tända lampornas färgsekvens till en upprepning av RGB.

Begränsningar

• $1 \le N \le 200\,000$.
• $S$ är en sträng med längden $N$.
• Varje tecken i $S$ är 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$ är heltal.

Deluppgifter

1. ($4$ poäng) $N = 3$.
2. ($22$ poäng) $N \le 300$.
3. ($19$ poäng) $N \le 10\,000$.
4. ($9$ poäng) $N$ är en multipel av $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ poäng) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ poäng) Inga ytterligare begränsningar.

Indata

Indata ges i följande format: $N$ $S$ $A \ B \ C$

Utdata

Skriv ut den minsta summan pengar som krävs för att göra de tända lampornas färgsekvens till en upprepning av RGB på $1$ rad, utan enhet (yen).

Exempel

6
GRBBRG
3 4 5

16

Till exempel, när $4$ operationer utförs enligt följande, blir de tända lampornas färgsekvens en upprepning av RGB. En släckt lampa representeras av -.

1. Betala $3$ yen för att släcka lampa $1$, som är den tända lampan längst till vänster. Lampornas tillstånd representeras av strängen -RBBRG.
2. Betala $4$ yen för att släcka lampa $6$, som är den tända lampan längst till höger. Lampornas tillstånd representeras av strängen -RBBR-.
3. Betala $4$ yen för att släcka lampa $5$, som är den tända lampan längst till höger. Lampornas tillstånd representeras av strängen -RBB--.
4. Betala $5$ yen för att välja lampa $3$ och tända om den i grönt. Lampornas tillstånd representeras av strängen -RGB--.

Eftersom det är omöjligt att göra färgsekvensen till en upprepning av RGB genom att betala mindre än $16$ yen, skrivs $16$ ut.

Detta exempel uppfyller begränsningarna för deluppgifterna $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Till exempel, när $3$ operationer utförs enligt följande, blir de tända lampornas färgsekvens en upprepning av RGB. En släckt lampa representeras av -.

1. Betala $1$ yen för att välja lampa $2$ och tända om den i grönt. Lampornas tillstånd representeras av strängen BGG.
2. Betala $1$ yen för att välja lampa $3$ och tända om den i blått. Lampornas tillstånd representeras av strängen BGB.
3. Betala $1$ yen för att välja lampa $1$ och tända om den i rött. Lampornas tillstånd representeras av strängen RGB.

Eftersom det är omöjligt att göra färgsekvensen till en upprepning av RGB genom att betala mindre än $3$ yen, skrivs $3$ ut.

Detta exempel uppfyller begränsningarna för deluppgifterna $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

Till exempel, när $3$ operationer utförs enligt följande, blir de tända lampornas färgsekvens en upprepning av RGB. En släckt lampa representeras av -.

1. Betala $9$ yen för att släcka lampa $1$, som är den tända lampan längst till vänster. Lampornas tillstånd representeras av strängen -RB.
2. Betala $9$ yen för att släcka lampa $2$, som är den tända lampan längst till vänster. Lampornas tillstånd representeras av strängen --B.
3. Betala $9$ yen för att släcka lampa $3$, som är den tända lampan längst till vänster. Lampornas tillstånd representeras av strängen ---.

Eftersom det är omöjligt att göra färgsekvensen till en upprepning av RGB genom att betala mindre än $27$ yen, skrivs $27$ ut. Observera att även fallet där det finns $0$ tända lampor uppfyller villkoret.

Detta exempel uppfyller begränsningarna för deluppgifterna $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Eftersom lampornas färgsekvens redan är en upprepning av RGB, skrivs $0$ ut.

Detta exempel uppfyller begränsningarna för deluppgifterna $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Detta exempel uppfyller begränsningarna för deluppgifterna $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Detta exempel uppfyller begränsningarna för deluppgifterna $2, 3, 6$.