Deskripsi Masalah

Terdapat $N$ lampu yangเรียง dalam satu baris horizontal, dinomori dari $1$ hingga $N$ dari kiri ke kanan. Warna setiap lampu adalah merah, hijau, atau biru. Warna lampu dinyatakan oleh sebuah string $S$, di mana warna lampu $i$ ($1 \le i \le N$) adalah merah ketika karakter ke-$i$ dari $S$ adalah R, hijau ketika G, dan biru ketika B. Pada awalnya, semua lampu menyala.

Selama terdapat setidaknya $1$ lampu yang menyala, JOI-kun dapat melakukan $3$ jenis operasi berikut dalam urutan apa pun dan berapa kali pun (melakukan $0$ operasi juga diperbolehkan):

• Membayar $A$ yen untuk mematikan lampu paling kiri di antara lampu-lampu yang sedang menyala.
• Membayar $B$ yen untuk mematikan lampu paling kanan di antara lampu-lampu yang sedang menyala.
• Membayar $C$ yen untuk memilih $1$ lampu yang sedang menyala dan menyalakannya kembali dengan warna apa pun yang ia sukai.

JOI-kun ingin barisan lampu ini terlihat berwarna putih yang indah ketika dilihat dari jauh. Untuk itu, urutan warna lampu yang menyala ketika dilihat dari kiri ke kanan harus berupa pengulangan RGB (merah, hijau, biru) seperti RGBRGB...RGB. Namun, kasus di mana terdapat $0$ lampu yang menyala juga dianggap sebagai pengulangan RGB. Perhatikan bahwa urutan warna seperti GBRGBR atau RGBRG tidak memenuhi kondisi.

Diberikan informasi mengenai lampu dan biaya yang diperlukan untuk operasi, buatlah program untuk mencari jumlah uang minimum yang diperlukan agar urutan warna lampu yang menyala menjadi pengulangan RGB.

Batasan

• $1 \le N \le 200\,000$.
• $S$ adalah string dengan panjang $N$.
• Setiap karakter dari $S$ adalah R, G, atau B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ adalah bilangan bulat.

Subsoal

1. ($4$ poin) $N = 3$.
2. ($22$ poin) $N \le 300$.
3. ($19$ poin) $N \le 10\,000$.
4. ($9$ poin) $N$ adalah kelipatan $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ poin) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dalam format berikut: $N$ $S$ $A \ B \ C$

Keluaran

Keluarkan jumlah uang minimum yang diperlukan untuk membuat urutan warna lampu yang menyala menjadi pengulangan RGB dalam $1$ baris, tanpa satuan (yen).

Contoh Masukan dan Keluaran

6
GRBBRG
3 4 5

16

Sebagai contoh, ketika $4$ operasi dilakukan sebagai berikut, urutan warna lampu yang menyala menjadi pengulangan RGB. Lampu yang mati dinyatakan dengan -.

1. Membayar $3$ yen untuk mematikan lampu $1$, yaitu lampu paling kiri yang menyala. Keadaan masing-masing lampu dinyatakan oleh string -RBBRG.
2. Membayar $4$ yen untuk mematikan lampu $6$, yaitu lampu paling kanan yang menyala. Keadaan masing-masing lampu dinyatakan oleh string -RBBR-.
3. Membayar $4$ yen untuk mematikan lampu $5$, yaitu lampu paling kanan yang menyala. Keadaan masing-masing lampu dinyatakan oleh string -RBB--.
4. Membayar $5$ yen untuk memilih lampu $3$ dan menyalakannya kembali menjadi warna hijau. Keadaan masing-masing lampu dinyatakan oleh string -RGB--.

Karena tidak mungkin membuat urutan warna lampu yang menyala menjadi pengulangan RGB dengan membayar kurang dari $16$ yen, keluarkan $16$.

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Sebagai contoh, ketika $3$ operasi dilakukan sebagai berikut, urutan warna lampu yang menyala menjadi pengulangan RGB. Lampu yang mati dinyatakan dengan -.

1. Membayar $1$ yen untuk memilih lampu $2$ dan menyalakannya kembali menjadi warna hijau. Keadaan masing-masing lampu dinyatakan oleh string BGG.
2. Membayar $1$ yen untuk memilih lampu $3$ dan menyalakannya kembali menjadi warna biru. Keadaan masing-masing lampu dinyatakan oleh string BGB.
3. Membayar $1$ yen untuk memilih lampu $1$ dan menyalakannya kembali menjadi warna merah. Keadaan masing-masing lampu dinyatakan oleh string RGB.

Karena tidak mungkin membuat urutan warna lampu yang menyala menjadi pengulangan RGB dengan membayar kurang dari $3$ yen, keluarkan $3$.

Contoh masukan ini memenuhi batasan Subsoal $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

Sebagai contoh, ketika $3$ operasi dilakukan sebagai berikut, urutan warna lampu yang menyala menjadi pengulangan RGB. Lampu yang mati dinyatakan dengan -.

1. Membayar $9$ yen untuk mematikan lampu $1$, yaitu lampu paling kiri yang menyala. Keadaan masing-masing lampu dinyatakan oleh string -RB.
2. Membayar $9$ yen untuk mematikan lampu $2$, yaitu lampu paling kiri yang menyala. Keadaan masing-masing lampu dinyatakan oleh string --B.
3. Membayar $9$ yen untuk mematikan lampu $3$, yaitu lampu paling kiri yang menyala. Keadaan masing-masing lampu dinyatakan oleh string ---.

Karena tidak mungkin membuat urutan warna lampu yang menyala menjadi pengulangan RGB dengan membayar kurang dari $27$ yen, keluarkan $27$. Perhatikan bahwa kasus di mana terdapat $0$ lampu yang menyala juga memenuhi kondisi.

Contoh masukan ini memenuhi batasan Subsoal $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Karena urutan warna lampu sudah merupakan pengulangan RGB, keluarkan $0$.

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Contoh masukan ini memenuhi batasan Subsoal $2, 3, 6$.