Tehtävänanto

$N$ valoa on asetettu vaakasuoraan riviin ja numeroitu vasemmalta oikealle luvuilla $1$:stä $N$:ään. Jokaisen valon väri on joko punainen, vihreä tai sininen. Valojen värit esitetään merkkijonolla $S$, missä valon $i$ ($1 \le i \le N$) väri on punainen, kun merkkijonon $S$ $i$:s merkki on R, vihreä, kun se on G, ja sininen, kun se on B. Aluksi kaikki valot palavat.

Niin kauan kuin vähintään $1$ valo palaa, JOI-kun voi suorittaa seuraavia $3$ tyyppisiä operaatioita haluamassaan järjestyksessä ja haluamansa määrän kertoja. Operaatioita ei ole pakko suorittaa edes $1$ kertaa.

• Maksa $A$ jeniä ja sammuta palavista valoista äärimmäisenä vasemmalla oleva valo.
• Maksa $B$ jeniä ja sammuta palavista valoista äärimmäisenä oikealla oleva valo.
• Maksa $C$ jeniä, valitse $1$ palava valo ja sytytä se uudelleen haluamasi väriseksi.

JOI-kun haluaa, että tämä valorivi näyttää kaukaa katsottuna kauniin valkoiselta. Tätä varten palavien valojen värijärjestyksen vasemmalta katsottuna täytyy olla merkkijonon RGB (punainen-vihreä-sininen) toistoa, kuten RGBRGB...RGB. Myös tapaus, jossa yksikään ($1$) valo ei pala, katsotaan merkkijonon RGB toistoksi. Huomaa, että värijärjestykset kuten GBRGBR tai RGBRG eivät täytä ehtoa.

Kun tiedot valoista ja operaatioihin tarvittavista rahamääristä on annettu, kirjoita ohjelma, joka etsii pienimmän rahamäärän, jolla palavien valojen värijärjestys saadaan muutetuksi merkkijonon RGB toistoksi.

Rajoitukset

• $1 \le N \le 200000$.
• $S$ on pituuden $N$ merkkijono.
• Jokainen merkkijonon $S$ merkki on joko R, G tai B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ ovat kokonaislukuja.

Osatehtävät

1. ($4$ pistettä) $N = 3$.
2. ($22$ pistettä) $N \le 300$.
3. ($19$ pistettä) $N \le 10000$.
4. ($9$ pistettä) $N$ on luvun $3$ monikerta, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ pistettä) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ pistettä) Ei lisärajoituksia.

Syöte

Syöte annetaan seuraavassa muodossa:

N
S
A B C

Tuloste

Tulosta $1$ riville pienin rahamäärä, joka tarvitaan palavien valojen värijärjestyksen muuttamiseksi merkkijonon RGB toistoksi, ilman yksikköä (jeniä).

Esimerkki 1

Syöte

6
GRBBRG
3 4 5

Tuloste

16

Kun esimerkiksi suoritetaan $4$ operaatiota seuraavasti, palavien valojen värijärjestyksestä tulee merkkijonon RGB toisto. Sammutetut valot merkitään merkillä -.

1. Maksa $3$ jeniä ja sammuta palavista valoista äärimmäisenä vasemmalla oleva valo $1$. Valojen tilaa kuvaa merkkijono -RBBRG.
2. Maksa $4$ jeniä ja sammuta palavista valoista äärimmäisenä oikealla oleva valo $6$. Valojen tilaa kuvaa merkkijono -RBBR-.
3. Maksa $4$ jeniä ja sammuta palavista valoista äärimmäisenä oikealla oleva valo $5$. Valojen tilaa kuvaa merkkijono -RBB--.
4. Maksa $5$ jeniä, valitse valo $3$ ja sytytä se uudelleen vihreäksi. Valojen tilaa kuvaa merkkijono -RGB--.

Koska palavien valojen värijärjestystä ei voida muuttaa merkkijonon RGB toistoksi maksamalla vähemmän kuin $16$ jeniä, tulostetaan $16$.

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 6$ rajoitukset.

Esimerkki 2

Syöte

3
BRG
1000000000 1000000000 1

Tuloste

3

Kun esimerkiksi suoritetaan $3$ operaatiota seuraavasti, palavien valojen värijärjestyksestä tulee merkkijonon RGB toisto. Sammutetut valot merkitään merkillä -.

1. Maksa $1$ jeni, valitse valo $2$ ja sytytä se uudelleen vihreäksi. Valojen tilaa kuvaa merkkijono BGG.
2. Maksa $1$ jeni, valitse valo $3$ ja sytytä se uudelleen siniseksi. Valojen tilaa kuvaa merkkijono BGB.
3. Maksa $1$ jeni, valitse valo $1$ ja sytytä se uudelleen punaiseksi. Valojen tilaa kuvaa merkkijono RGB.

Koska palavien valojen värijärjestystä ei voida muuttaa merkkijonon RGB toistoksi maksamalla vähemmän kuin $3$ jeniä, tulostetaan $3$.

Tämä syöteesimerkki täyttää osatehtävien $1, 2, 3, 4, 5, 6$ rajoitukset.

Esimerkki 3

Syöte

3
GRB
9 11 14

Tuloste

27

Kun esimerkiksi suoritetaan $3$ operaatiota seuraavasti, palavien valojen värijärjestyksestä tulee merkkijonon RGB toisto. Sammutetut valot merkitään merkillä -.

1. Maksa $9$ jeniä ja sammuta palavista valoista äärimmäisenä vasemmalla oleva valo $1$. Valojen tilaa kuvaa merkkijono -RB.
2. Maksa $9$ jeniä ja sammuta palavista valoista äärimmäisenä vasemmalla oleva valo $2$. Valojen tilaa kuvaa merkkijono --B.
3. Maksa $9$ jeniä ja sammuta palavista valoista äärimmäisenä vasemmalla oleva valo $3$. Valojen tilaa kuvaa merkkijono ---.

Koska palavien valojen värijärjestystä ei voida muuttaa merkkijonon RGB toistoksi maksamalla vähemmän kuin $27$ jeniä, tulostetaan $27$. Huomaa, että myös tapaus, jossa yksikään ($1$) valo ei pala, täyttää ehdon.

Tämä syöteesimerkki täyttää osatehtävien $1, 2, 3, 6$ rajoitukset.

Esimerkki 4

Syöte

9
RGBRGBRGB
1000000000 1000000000 1

Tuloste

0

Koska valojen värijärjestys on jo valmiiksi merkkijonon RGB toisto, tulostetaan $0$.

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 4, 5, 6$ rajoitukset.

Esimerkki 5

Syöte

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

Tuloste

2000000008

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 5, 6$ rajoitukset.

Esimerkki 6

Syöte

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

Tuloste

10107224827

Tämä syöteesimerkki täyttää osatehtävien $2, 3, 6$ rajoitukset.