Lýsing á verkefni

$N$ ljós eru í láréttri röð og eru númeruð frá $1$ til $N$ í röð frá vinstri til hægri. Litur hvers ljóss er annaðhvort rauður, grænn eða blár. Litir ljósanna eru táknaðir með streng $S$, þar sem litur ljóss $i$ ($1 \le i \le N$) er rauður þegar $i$-ti stafurinn í $S$ er R, grænn þegar hann er G og blár þegar hann er B. Í upphafi eru öll ljósin kveikt.

Meðan að minnsta kosti $1$ ljós er kveikt getur JOI-kun framkvæmt eftirfarandi $3$ tegundir aðgerða í hvaða röð sem er og eins oft og hann vill. Það er líka í lagi að framkvæma enga aðgerð, ekki einu sinni $1$ sinni.

• Borga $A$ jen til að slökkva á því ljósi sem er lengst til vinstri af þeim ljósum sem eru kveikt.
• Borga $B$ jen til að slökkva á því ljósi sem er lengst til hægri af þeim ljósum sem eru kveikt.
• Borga $C$ jen til að velja $1$ kveikt ljós og kveikja á því aftur í hvaða lit sem er.

JOI-kun vill að þessi ljósaröð líti út eins og fallegur hvítur litur þegar horft er á hana úr fjarlægð. Til þess þarf litaröð kveiktu ljósanna, séð frá vinstri, að vera endurtekning á RGB (rauður-grænn-blár) eins og RGBRGB...RGB. Hins vegar telst tilfellið þar sem ekki einu sinni $1$ ljós er kveikt líka vera endurtekning á RGB. Athugið að litaraðir eins og GBRGBR eða RGBRG uppfylla ekki skilyrðið.

Gefnar eru upplýsingar um ljósin og upphæðirnar sem þarf fyrir aðgerðirnar. Skrifaðu forrit til að finna lágmarksupphæðina sem þarf til að gera litaröð kveiktu ljósanna að endurtekningu á RGB.

Takmarkanir

• $1 \le N \le 200000$.
• $S$ er strengur af lengd $N$.
• Hver stafur í $S$ er R, G eða B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ eru heiltölur.

Undirverkefni

1. ($4$ stig) $N = 3$.
2. ($22$ stig) $N \le 300$.
3. ($19$ stig) $N \le 10000$.
4. ($9$ stig) $N$ er margfeldi af $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ stig) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ stig) Engar viðbótartakmarkanir.

Inntak

Inntakið er gefið á eftirfarandi sniði:

N
S
A B C

Úttak

Skrifaðu út á $1$ línu lágmarksupphæðina sem þarf til að gera litaröð kveiktu ljósanna að endurtekningu á RGB, án einingar (jen).

Dæmi 1

Inntak

6
GRBBRG
3 4 5

Úttak

16

Til dæmis, þegar $4$ aðgerðir eru framkvæmdar á eftirfarandi hátt, verður litaröð kveiktu ljósanna endurtekning á RGB. Slökkt ljós eru táknuð með -.

1. Borga $3$ jen til að slökkva á ljósi $1$, sem er lengst til vinstri af kveiktu ljósunum. Ástand hvers ljóss er táknað með strengnum -RBBRG.
2. Borga $4$ jen til að slökkva á ljósi $6$, sem er lengst til hægri af kveiktu ljósunum. Ástand hvers ljóss er táknað með strengnum -RBBR-.
3. Borga $4$ jen til að slökkva á ljósi $5$, sem er lengst til hægri af kveiktu ljósunum. Ástand hvers ljóss er táknað með strengnum -RBB--.
4. Borga $5$ jen til að velja ljós $3$ og kveikja á því aftur í grænum lit. Ástand hvers ljóss er táknað með strengnum -RGB--.

Þar sem ekki er hægt að gera litaröð kveiktu ljósanna að endurtekningu á RGB með því að borga minna en $16$ jen, er $16$ skrifað út.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 6$.

Dæmi 2

Inntak

3
BRG
1000000000 1000000000 1

Úttak

3

Til dæmis, þegar $3$ aðgerðir eru framkvæmdar á eftirfarandi hátt, verður litaröð kveiktu ljósanna endurtekning á RGB. Slökkt ljós eru táknuð með -.

1. Borga $1$ jen til að velja ljós $2$ og kveikja á því aftur í grænum lit. Ástand hvers ljóss er táknað með strengnum BGG.
2. Borga $1$ jen til að velja ljós $3$ og kveikja á því aftur í bláum lit. Ástand hvers ljóss er táknað með strengnum BGB.
3. Borga $1$ jen til að velja ljós $1$ og kveikja á því aftur í rauðum lit. Ástand hvers ljóss er táknað með strengnum RGB.

Þar sem ekki er hægt að gera litaröð kveiktu ljósanna að endurtekningu á RGB með því að borga minna en $3$ jen, er $3$ skrifað út.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $1, 2, 3, 4, 5, 6$.

Dæmi 3

Inntak

3
GRB
9 11 14

Úttak

27

Til dæmis, þegar $3$ aðgerðir eru framkvæmdar á eftirfarandi hátt, verður litaröð kveiktu ljósanna endurtekning á RGB. Slökkt ljós eru táknuð með -.

1. Borga $9$ jen til að slökkva á ljósi $1$, sem er lengst til vinstri af kveiktu ljósunum. Ástand hvers ljóss er táknað með strengnum -RB.
2. Borga $9$ jen til að slökkva á ljósi $2$, sem er lengst til vinstri af kveiktu ljósunum. Ástand hvers ljóss er táknað með strengnum --B.
3. Borga $9$ jen til að slökkva á ljósi $3$, sem er lengst til vinstri af kveiktu ljósunum. Ástand hvers ljóss er táknað með strengnum ---.

Þar sem ekki er hægt að gera litaröð kveiktu ljósanna að endurtekningu á RGB með því að borga minna en $27$ jen, er $27$ skrifað út. Athugið að tilfellið þar sem ekki einu sinni $1$ ljós er kveikt uppfyllir einnig skilyrðið.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $1, 2, 3, 6$.

Dæmi 4

Inntak

9
RGBRGBRGB
1000000000 1000000000 1

Úttak

0

Þar sem litaröð ljósanna er nú þegar endurtekning á RGB, er $0$ skrifað út.

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 4, 5, 6$.

Dæmi 5

Inntak

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

Úttak

2000000008

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 5, 6$.

Dæmi 6

Inntak

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

Úttak

10107224827

Þetta inntaksdæmi uppfyllir takmarkanir undirverkefna $2, 3, 6$.