Условие задачи

В горизонтальный ряд расположены $N$ лампочек, пронумерованных слева направо от $1$ до $N$. Цвет каждой лампочки — красный, зелёный или синий. Цвета лампочек задаются строкой $S$: цвет лампочки $i$ ($1 \le i \le N$) красный, если $i$-й символ строки $S$ равен R, зелёный — если G, и синий — если B. Изначально все лампочки включены.

Пока есть хотя бы $1$ включённая лампочка, Джой-кун может выполнять следующие $3$ типа операций в любом порядке любое количество раз (также можно выполнить $0$ операций):

• Заплатить $A$ иен и выключить самую левую из горящих лампочек.
• Заплатить $B$ иен и выключить самую правую из горящих лампочек.
• Заплатить $C$ иен, выбрать $1$ горящую лампочку и переключить её на любой желаемый цвет.

Джой-кун хочет, чтобы издалека этот ряд лампочек выглядел как красивый белый свет. Для этого последовательность цветов горящих лампочек слева направо должна представлять собой повторение RGB (красный, зелёный, синий), например RGBRGB...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$

Выходные данные

Выведите в $1$ строке минимальную сумму денег, необходимую для того, чтобы последовательность цветов горящих лампочек стала повторением RGB, без указания единицы измерения (иен).

Примеры

6
GRBBRG
3 4 5

16

Например, если выполнить $4$ операции следующим образом, последовательность цветов горящих лампочек станет повторением RGB. Выключенная лампочка обозначается символом -.

1. Заплатить $3$ иены и выключить самую левую горящую лампочку $1$. Состояние лампочек описывается строкой -RBBRG.
2. Заплатить $4$ иены и выключить самую правую горящую лампочку $6$. Состояние лампочек описывается строкой -RBBR-.
3. Заплатить $4$ иены и выключить самую правую горящую лампочку $5$. Состояние лампочек описывается строкой -RBB--.
4. Заплатить $5$ иен, выбрать лампочку $3$ и переключить её на зелёный цвет. Состояние лампочек описывается строкой -RGB--.

Поскольку невозможно сделать последовательность цветов горящих лампочек повторением RGB, заплатив менее $16$ иен, выводим $16$.

Этот пример удовлетворяет ограничениям подзадач $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Например, если выполнить $3$ операции следующим образом, последовательность цветов горящих лампочек станет повторением RGB. Выключенная лампочка обозначается символом -.

1. Заплатить $1$ иену, выбрать лампочку $2$ и переключить её на зелёный цвет. Состояние лампочек описывается строкой BGG.
2. Заплатить $1$ иену, выбрать лампочку $3$ и переключить её на синий цвет. Состояние лампочек описывается строкой BGB.
3. Заплатить $1$ иену, выбрать лампочку $1$ и переключить её на красный цвет. Состояние лампочек описывается строкой RGB.

Поскольку невозможно сделать последовательность цветов горящих лампочек повторением RGB, заплатив менее $3$ иен, выводим $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$. Состояние лампочек описывается строкой ---.

Поскольку невозможно сделать последовательность цветов горящих лампочек повторением RGB, заплатив менее $27$ иен, выводим $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$.