Enunciado del problema

Hay $N$ luces dispuestas en una fila horizontal, numeradas del $1$ al $N$ de izquierda a derecha. El color de cada luz es rojo, verde o azul. Los colores de las luces se representan mediante una cadena $S$, donde el color de la luz $i$ ($1 \le i \le N$) es rojo cuando el $i$-ésimo carácter de $S$ es R, verde cuando es G y azul cuando es B. Inicialmente, todas las luces están encendidas.

Mientras haya al menos $1$ luz encendida, JOI-kun puede realizar los siguientes $3$ tipos de operaciones en cualquier orden y cualquier número de veces (también puede realizar $0$ operaciones):

• Pagar $A$ yenes para apagar la luz encendida que esté más a la izquierda.
• Pagar $B$ yenes para apagar la luz encendida que esté más a la derecha.
• Pagar $C$ yenes para elegir $1$ luz encendida y volver a encenderla del color que prefiera.

JOI-kun quiere que esta fila de luces se vea de un hermoso color blanco cuando se mire desde lejos. Para ello, la secuencia de colores de las luces encendidas vistas de izquierda a derecha debe ser una repetición de RGB (rojo, verde, azul) como RGBRGB...RGB. Sin embargo, el caso en el que hay $0$ luces encendidas también se considera una repetición de RGB. Ten en cuenta que secuencias de colores como GBRGBR o RGBRG no cumplen la condición.

Dada la información sobre las luces y los costos necesarios para las operaciones, escribe un programa para encontrar la cantidad mínima de dinero necesaria para hacer que la secuencia de colores de las luces encendidas sea una repetición de RGB.

Restricciones

• $1 \le N \le 200\,000$.
• $S$ es una cadena de longitud $N$.
• Cada carácter de $S$ es 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$ son números enteros.

Subtareas

1. ($4$ puntos) $N = 3$.
2. ($22$ puntos) $N \le 300$.
3. ($19$ puntos) $N \le 10\,000$.
4. ($9$ puntos) $N$ es múltiplo de $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ puntos) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ puntos) Sin restricciones adicionales.

Entrada

La entrada se proporciona en el siguiente formato: $N$ $S$ $A \ B \ C$

Salida

Imprime en $1$ línea la cantidad mínima de dinero necesaria para que la secuencia de colores de las luces encendidas sea una repetición de RGB, omitiendo la unidad (yenes).

Ejemplo de entrada y salida

6
GRBBRG
3 4 5

16

Por ejemplo, cuando se realizan $4$ operaciones de la siguiente manera, la secuencia de colores de las luces encendidas se convierte en una repetición de RGB. Una luz apagada se representa con -.

1. Pagar $3$ yenes para apagar la luz $1$, que es la luz encendida más a la izquierda. El estado de las luces se representa mediante la cadena -RBBRG.
2. Pagar $4$ yenes para apagar la luz $6$, que es la luz encendida más a la derecha. El estado de las luces se representa mediante la cadena -RBBR-.
3. Pagar $4$ yenes para apagar la luz $5$, que es la luz encendida más a la derecha. El estado de las luces se representa mediante la cadena -RBB--.
4. Pagar $5$ yenes para elegir la luz $3$ y volver a encenderla en verde. El estado de las luces se representa mediante la cadena -RGB--.

Como es imposible lograr una repetición de RGB pagando menos de $16$ yenes, se imprime $16$.

Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Por ejemplo, cuando se realizan $3$ operaciones de la siguiente manera, la secuencia de colores de las luces encendidas se convierte en una repetición de RGB. Una luz apagada se representa con -.

1. Pagar $1$ yen para elegir la luz $2$ y volver a encenderla en verde. El estado de las luces se representa mediante la cadena BGG.
2. Pagar $1$ yen para elegir la luz $3$ y volver a encenderla en azul. El estado de las luces se representa mediante la cadena BGB.
3. Pagar $1$ yen para elegir la luz $1$ y volver a encenderla en rojo. El estado de las luces se representa mediante la cadena RGB.

Como es imposible lograr una repetición de RGB pagando menos de $3$ yenes, se imprime $3$.

Este ejemplo de entrada cumple las restricciones de las subtareas $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

Por ejemplo, cuando se realizan $3$ operaciones de la siguiente manera, la secuencia de colores de las luces encendidas se convierte en una repetición de RGB. Una luz apagada se representa con -.

1. Pagar $9$ yenes para apagar la luz $1$, que es la luz encendida más a la izquierda. El estado de las luces se representa mediante la cadena -RB.
2. Pagar $9$ yenes para apagar la luz $2$, que es la luz encendida más a la izquierda. El estado de las luces se representa mediante la cadena --B.
3. Pagar $9$ yenes para apagar la luz $3$, que es la luz encendida más a la izquierda. El estado de las luces se representa mediante la cadena ---.

Como es imposible lograr una repetición de RGB pagando menos de $27$ yenes, se imprime $27$. Ten en cuenta que el caso en que hay $0$ luces encendidas también cumple la condición.

Este ejemplo de entrada cumple las restricciones de las subtareas $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Como la secuencia de colores de las luces ya es una repetición de RGB, se imprime $0$.

Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Este ejemplo de entrada cumple las restricciones de las subtareas $2, 3, 6$.