Testo del problema

Ci sono $N$ luci disposte in una fila orizzontale, numerate da $1$ a $N$ da sinistra a destra. Il colore di ciascuna luce è rosso, verde o blu. I colori delle luci sono rappresentati da una stringa $S$, dove il colore della luce $i$ ($1 \le i \le N$) è rosso quando l'$i$-esimo carattere di $S$ è R, verde quando è G e blu quando è B. Inizialmente, tutte le luci sono accese.

Finché c'è almeno $1$ luce accesa, JOI-kun può eseguire i seguenti $3$ tipi di operazioni in qualsiasi ordine e qualsiasi numero di volte (è anche consentito eseguire $0$ operazioni):

• Pagare $A$ yen per spegnere la luce accesa più a sinistra.
• Pagare $B$ yen per spegnere la luce accesa più a destra.
• Pagare $C$ yen per scegliere $1$ luce accesa e riaccenderla del colore che preferisce.

JOI-kun vuole che questa fila di luci appaia di un bel colore bianco quando viene vista da lontano. A tal fine, la sequenza dei colori delle luci accese viste da sinistra a destra deve essere una ripetizione di RGB (rosso, verde, blu) come RGBRGB...RGB. Tuttavia, anche il caso in cui ci sono $0$ luci accese è considerato una ripetizione di RGB. Si noti che sequenze di colori come GBRGBR o RGBRG non soddisfano la condizione.

Date le informazioni sulle luci e sui costi necessari per le operazioni, scrivi un programma per trovare la quantità minima di denaro necessaria per rendere la sequenza dei colori delle luci accese una ripetizione di RGB.

Vincoli

• $1 \le N \le 200\,000$.
• $S$ è una stringa di lunghezza $N$.
• Ogni carattere di $S$ è R, G o B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ sono numeri interi.

Sottoproblemi

1. ($4$ punti) $N = 3$.
2. ($22$ punti) $N \le 300$.
3. ($19$ punti) $N \le 10\,000$.
4. ($9$ punti) $N$ è un multiplo di $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ punti) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ punti) Nessun vincolo aggiuntivo.

Input

L'input è fornito nel seguente formato: $N$ $S$ $A \ B \ C$

Output

Stampa su $1$ riga la quantità minima di denaro necessaria per rendere la sequenza dei colori delle luci accese una ripetizione di RGB, omettendo l'unità di misura (yen).

Esempi di input e output

6
GRBBRG
3 4 5

16

Ad esempio, eseguendo $4$ operazioni come segue, la sequenza dei colori delle luci accese diventa una ripetizione di RGB. Una luce spenta è rappresentata da -.

1. Pagare $3$ yen per spegnere la luce $1$, che è la luce accesa più a sinistra. Lo stato delle luci è rappresentato dalla stringa -RBBRG.
2. Pagare $4$ yen per spegnere la luce $6$, che è la luce accesa più a destra. Lo stato delle luci è rappresentato dalla stringa -RBBR-.
3. Pagare $4$ yen per spegnere la luce $5$, che è la luce accesa più a destra. Lo stato delle luci è rappresentato dalla stringa -RBB--.
4. Pagare $5$ yen per scegliere la luce $3$ e riaccenderla di verde. Lo stato delle luci è rappresentato dalla stringa -RGB--.

Poiché è impossibile ottenere una ripetizione di RGB pagando meno di $16$ yen, si stampa $16$.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Ad esempio, eseguendo $3$ operazioni come segue, la sequenza dei colori delle luci accese diventa una ripetizione di RGB. Una luce spenta è rappresentata da -.

1. Pagare $1$ yen per scegliere la luce $2$ e riaccenderla di verde. Lo stato delle luci è rappresentato dalla stringa BGG.
2. Pagare $1$ yen per scegliere la luce $3$ e riaccenderla di blu. Lo stato delle luci è rappresentato dalla stringa BGB.
3. Pagare $1$ yen per scegliere la luce $1$ e riaccenderla di rosso. Lo stato delle luci è rappresentato dalla stringa RGB.

Poiché è impossibile ottenere una ripetizione di RGB pagando meno di $3$ yen, si stampa $3$.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

Ad esempio, eseguendo $3$ operazioni come segue, la sequenza dei colori delle luci accese diventa una ripetizione di RGB. Una luce spenta è rappresentata da -.

1. Pagare $9$ yen per spegnere la luce $1$, che è la luce accesa più a sinistra. Lo stato delle luci è rappresentato dalla stringa -RB.
2. Pagare $9$ yen per spegnere la luce $2$, che è la luce accesa più a sinistra. Lo stato delle luci è rappresentato dalla stringa --B.
3. Pagare $9$ yen per spegnere la luce $3$, che è la luce accesa più a sinistra. Lo stato delle luci è rappresentato dalla stringa ---.

Poiché è impossibile ottenere una ripetizione di RGB pagando meno di $27$ yen, si stampa $27$. Si noti che anche il caso in cui ci sono $0$ luci accese soddisfa la condizione.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Poiché la sequenza dei colori delle luci è già una ripetizione di RGB, si stampa $0$.

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Questo esempio di input soddisfa i vincoli dei sottoproblemi $2, 3, 6$.