Énoncé du problème

Il y a $N$ lampes alignées horizontalement, numérotées de $1$ à $N$ de gauche à droite. La couleur de chaque lampe est rouge, vert ou bleu. Les couleurs des lampes sont représentées par une chaîne de caractères $S$, où la couleur de la lampe $i$ ($1 \le i \le N$) est rouge lorsque le $i$-ème caractère de $S$ est R, vert lorsqu'il est G et bleu lorsqu'il est B. Initialement, toutes les lampes sont allumées.

Tant qu'il reste au moins $1$ lampe allumée, JOI-kun peut effectuer les $3$ types d'opérations suivants dans n'importe quel ordre et autant de fois qu'il le souhaite (il peut aussi effectuer $0$ opération) :

• Payer $A$ yens pour éteindre la lampe allumée la plus à gauche.
• Payer $B$ yens pour éteindre la lampe allumée la plus à droite.
• Payer $C$ yens pour choisir $1$ lampe allumée et la rallumer dans la couleur de son choix.

JOI-kun souhaite que cette rangée de lampes apparaisse d'un beau blanc lorsqu'on la regarde de loin. Pour cela, la séquence des couleurs des lampes allumées, lue de gauche à droite, doit être une répétition de RGB (rouge, vert, bleu) telle que RGBRGB...RGB. Toutefois, le cas où il y a $0$ lampe allumée est également considéré comme une répétition de RGB. Notez que des séquences de couleurs telles que GBRGBR ou RGBRG ne satisfont pas la condition.

Étant donné les informations sur les lampes et le coût des opérations, écrivez un programme permettant de trouver le montant minimal nécessaire pour que la séquence des couleurs des lampes allumées soit une répétition de RGB.

Contraintes

• $1 \le N \le 200\,000$.
• $S$ est une chaîne de caractères de longueur $N$.
• Chaque caractère de $S$ est R, G ou B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ sont des entiers.

Sous-tâches

1. ($4$ points) $N = 3$.
2. ($22$ points) $N \le 300$.
3. ($19$ points) $N \le 10\,000$.
4. ($9$ points) $N$ est un multiple de $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ points) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ points) Aucune contrainte supplémentaire.

Entrée

L'entrée est donnée dans le format suivant : $N$ $S$ $A \ B \ C$

Sortie

Affichez sur $1$ ligne le montant minimal nécessaire pour que la séquence des couleurs des lampes allumées soit une répétition de RGB, en omettant l'unité (yen).

Exemples d'entrée et de sortie

6
GRBBRG
3 4 5

16

Par exemple, lorsqu'on effectue $4$ opérations comme suit, la séquence des couleurs des lampes allumées devient une répétition de RGB. Une lampe éteinte est représentée par -.

1. Payer $3$ yens pour éteindre la lampe $1$, qui est la lampe allumée la plus à gauche. L'état des lampes est représenté par la chaîne -RBBRG.
2. Payer $4$ yens pour éteindre la lampe $6$, qui est la lampe allumée la plus à droite. L'état des lampes est représenté par la chaîne -RBBR-.
3. Payer $4$ yens pour éteindre la lampe $5$, qui est la lampe allumée la plus à droite. L'état des lampes est représenté par la chaîne -RBB--.
4. Payer $5$ yens pour choisir la lampe $3$ et la rallumer en vert. L'état des lampes est représenté par la chaîne -RGB--.

Comme il est impossible d'obtenir une répétition de RGB en payant moins de $16$ yens, on affiche $16$.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Par exemple, lorsqu'on effectue $3$ opérations comme suit, la séquence des couleurs des lampes allumées devient une répétition de RGB. Une lampe éteinte est représentée par -.

1. Payer $1$ yen pour choisir la lampe $2$ et la rallumer en vert. L'état des lampes est représenté par la chaîne BGG.
2. Payer $1$ yen pour choisir la lampe $3$ et la rallumer en bleu. L'état des lampes est représenté par la chaîne BGB.
3. Payer $1$ yen pour choisir la lampe $1$ et la rallumer en rouge. L'état des lampes est représenté par la chaîne RGB.

Comme il est impossible d'obtenir une répétition de RGB en payant moins de $3$ yens, on affiche $3$.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

Par exemple, lorsqu'on effectue $3$ opérations comme suit, la séquence des couleurs des lampes allumées devient une répétition de RGB. Une lampe éteinte est représentée par -.

1. Payer $9$ yens pour éteindre la lampe $1$, qui est la lampe allumée la plus à gauche. L'état des lampes est représenté par la chaîne -RB.
2. Payer $9$ yens pour éteindre la lampe $2$, qui est la lampe allumée la plus à gauche. L'état des lampes est représenté par la chaîne --B.
3. Payer $9$ yens pour éteindre la lampe $3$, qui est la lampe allumée la plus à gauche. L'état des lampes est représenté par la chaîne ---.

Comme il est impossible d'obtenir une répétition de RGB en payant moins de $27$ yens, on affiche $27$. Notez que le cas où il y a $0$ lampe allumée satisfait également la condition.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Comme la séquence des couleurs des lampes est déjà une répétition de RGB, on affiche $0$.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Cet exemple d'entrée satisfait les contraintes des sous-tâches $2, 3, 6$.