Есептің шарты

Көлденең қатарда солдан оңға қарай $1$-ден $N$-ге дейін нөмірленген $N$ шам орналасқан. Әрбір шамның түсі — қызыл, жасыл немесе көк. Шамдардың түстері $S$ жолымен беріледі: $S$ жолының $i$-ші таңбасы R болса, $i$-ші шамның ($1 \le i \le N$) түсі қызыл, G болса — жасыл, ал B болса — көк. Бастапқыда барлық шамдар жанып тұр.

Жанып тұрған кемінде $1$ шам бар болса, JOI-кун келесі $3$ түрлі операцияны кез келген ретпен кез келген рет орындай алады ($0$ рет орындауға да болады):

• $A$ иена төлеп, жанып тұрған шамдардың ішіндегі ең сол жақтағысын өшіру.
• $B$ иена төлеп, жанып тұрған шамдардың ішіндегі ең оң жақтағысын өшіру.
• $C$ иена төлеп, жанып тұрған $1$ шамды таңдап, оны қалаған түске қайта жағу.

JOI-кун бұл шамдар қатарына алыстан қарағанда әдемі ақ түсті болып көрінгенін қалайды. Ол үшін жанып тұрған шамдардың солдан оңға қарай түстер тізбегі RGBRGB...RGB сияқты RGB (қызыл, жасыл, көк) қайталануы болуы керек. Дегенмен, жанып тұрған $0$ шам болған жағдай да RGB қайталануы болып саналады. GBRGBR немесе RGBRG сияқты түстер тізбегі шартты қанағаттандырмайтынына назар аударыңыз.

Шамдар және операцияларға қажетті сомалар туралы ақпарат берілген. Жанып тұрған шамдардың түстер тізбегін RGB қайталануына айналдыру үшін қажетті ең аз ақша сомасын табатын бағдарлама жазыңыз.

Шектеулер

• $1 \le N \le 200\,000$.
• $S$ — ұзындығы $N$ болатын жол.
• $S$ жолының әрбір таңбасы — R, G немесе B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ — бүтін сандар.

Ішкі есептер

1. ($4$ ұпай) $N = 3$.
2. ($22$ ұпай) $N \le 300$.
3. ($19$ ұпай) $N \le 10\,000$.
4. ($9$ ұпай) $N$ саны $3$-ке еселік, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ ұпай) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ ұпай) Қосымша шектеулер жоқ.

Кіріс деректер

Кіріс деректер келесі форматта беріледі: $N$ $S$ $A \ B \ C$

Шығыс деректер

Жанып тұрған шамдардың түстер тізбегін RGB қайталануына айналдыру үшін қажетті ең аз ақша сомасын өлшем бірліксіз (иенасыз) $1$ жолда шығарыңыз.

Мысалдар

6
GRBBRG
3 4 5

16

Мысалы, келесідей $4$ операция орындалғанда, жанып тұрған шамдардың түстер тізбегі RGB қайталануына айналады. Өшірілген шам - таңбасымен белгіленеді.

1. $3$ иена төлеп, жанып тұрған шамдардың ең сол жағындағы $1$-ші шамды өшіру. Шамдардың күйі -RBBRG жолымен сипатталады.
2. $4$ иена төлеп, жанып тұрған шамдардың ең оң жағындағы $6$-шы шамды өшіру. Шамдардың күйі -RBBR- жолымен сипатталады.
3. $4$ иена төлеп, жанып тұрған шамдардың ең оң жағындағы $5$-ші шамды өшіру. Шамдардың күйі -RBB-- жолымен сипатталады.
4. $5$ иена төлеп, $3$-ші шамды таңдап, оны жасыл түске қайта жағу. Шамдардың күйі -RGB-- жолымен сипатталады.

$16$ иенадан аз төлеп, жанып тұрған шамдардың түстер тізбегін RGB қайталануына айналдыру мүмкін болмағандықтан, $16$ шығарылады.

Бұл мысал $2, 3, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

3
BRG
1000000000 1000000000 1

3

Мысалы, келесідей $3$ операция орындалғанда, жанып тұрған шамдардың түстер тізбегі RGB қайталануына айналады. Өшірілген шам - таңбасымен белгіленеді.

1. $1$ иена төлеп, $2$-ші шамды таңдап, оны жасыл түске қайта жағу. Шамдардың күйі BGG жолымен сипатталады.
2. $1$ иена төлеп, $3$-ші шамды таңдап, оны көк түске қайта жағу. Шамдардың күйі BGB жолымен сипатталады.
3. $1$ иена төлеп, $1$-ші шамды таңдап, оны қызыл түске қайта жағу. Шамдардың күйі RGB жолымен сипатталады.

$3$ иенадан аз төлеп, жанып тұрған шамдардың түстер тізбегін RGB қайталануына айналдыру мүмкін болмағандықтан, $3$ шығарылады.

Бұл мысал $1, 2, 3, 4, 5, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

3
GRB
9 11 14

27

Мысалы, келесідей $3$ операция орындалғанда, жанып тұрған шамдардың түстер тізбегі RGB қайталануына айналады. Өшірілген шам - таңбасымен белгіленеді.

1. $9$ иена төлеп, жанып тұрған шамдардың ең сол жағындағы $1$-ші шамды өшіру. Шамдардың күйі -RB жолымен сипатталады.
2. $9$ иена төлеп, жанып тұрған шамдардың ең сол жағындағы $2$-ші шамды өшіру. Шамдардың күйі --B жолымен сипатталады.
3. $9$ иена төлеп, жанып тұрған шамдардың ең сол жағындағы $3$-ші шамды өшіру. Шамдардың күйі --- жолымен сипатталады.

$27$ иенадан аз төлеп, жанып тұрған шамдардың түстер тізбегін RGB қайталануына айналдыру мүмкін болмағандықтан, $27$ шығарылады. Жанып тұрған $0$ шам болған жағдай да шартты қанағаттандыратынына назар аударыңыз.

Бұл мысал $1, 2, 3, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

9
RGBRGBRGB
1000000000 1000000000 1

0

Шамдардың түстер тізбегі қазірдің өзінде RGB қайталануы болғандықтан, $0$ шығарылады.

Бұл мысал $2, 3, 4, 5, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Бұл мысал $2, 3, 5, 6$ ішкі есептерінің шектеулерін қанағаттандырады.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Бұл мысал $2, 3, 6$ ішкі есептерінің шектеулерін қанағаттандырады.