Умова задачі

У горизонтальний ряд розташовано $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$.