Treść zadania

W poziomym rzędzie ustawionych jest $N$ lampek, ponumerowanych od $1$ do $N$ od lewej do prawej. Kolorem każdej lampki jest czerwony, zielony lub niebieski. Kolory lampek są reprezentowane przez napis $S$, gdzie kolor lampki $i$ ($1 \le i \le N$) jest czerwony, gdy $i$-tym znakiem napisu $S$ jest R, zielony, gdy jest to G, oraz niebieski, gdy jest to B. Początkowo wszystkie lampki są włączone.

Dopóki włączona jest co najmniej $1$ lampka, JOI-kun może wykonywać następujące $3$ rodzaje operacji w dowolnej kolejności i dowolną liczbę razy (dozwolone jest również wykonanie $0$ operacji):

• Zapłacić $A$ jenów, aby wyłączyć skrajnie lewą spośród aktualnie włączonych lampek.
• Zapłacić $B$ jenów, aby wyłączyć skrajnie prawą spośród aktualnie włączonych lampek.
• Zapłacić $C$ jenów, aby wybrać $1$ aktualnie włączoną lampkę i przełączyć ją na dowolny wybrany kolor.

JOI-kun chce, aby ten rząd lampek oglądany z daleka wyglądał jak piękne białe światło. W tym celu ciąg kolorów włączonych lampek patrząc od lewej do prawej musi być powtórzeniem RGB (czerwony, zielony, niebieski), takim jak RGBRGB...RGB. Przyjmujemy jednak, że przypadek, w którym włączonych jest $0$ lampek, również jest uznawany za powtórzenie RGB. Zauważ, że ciągi kolorów takie jak GBRGBR czy RGBRG nie spełniają warunku.

Mając dane informacje o lampkach oraz kosztach poszczególnych operacji, napisz program wyznaczający minimalną kwotę pieniędzy potrzebną do tego, aby ciąg kolorów włączonych lampek stał się powtórzeniem RGB.

Ograniczenia

• $1 \le N \le 200\,000$.
• $S$ jest napisem o długości $N$.
• Każdy znak napisu $S$ to R, G lub B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ są liczbami całkowitymi.

Podzadania

1. ($4$ punkty) $N = 3$.
2. ($22$ punkty) $N \le 300$.
3. ($19$ punktów) $N \le 10\,000$.
4. ($9$ punktów) $N$ jest wielokrotnością $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ punktów) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ punktów) Brak dodatkowych ograniczeń.

Wejście

Wejście podane jest w następującym formacie: $N$ $S$ $A \ B \ C$

Wyjście

Wypisz w $1$ wierszu minimalną kwotę pieniędzy potrzebną do tego, aby ciąg kolorów włączonych lampek stał się powtórzeniem RGB, pomijając jednostkę (jeny).

Przykłady

6
GRBBRG
3 4 5

16

Na przykład po wykonaniu $4$ operacji w poniższy sposób ciąg kolorów włączonych lampek staje się powtórzeniem RGB. Wyłączona lampka jest oznaczona znakiem -.

1. Zapłać $3$ jeny, aby wyłączyć lampkę $1$, czyli skrajnie lewą włączoną lampkę. Stan lampek jest reprezentowany przez napis -RBBRG.
2. Zapłać $4$ jeny, aby wyłączyć lampkę $6$, czyli skrajnie prawą włączoną lampkę. Stan lampek jest reprezentowany przez napis -RBBR-.
3. Zapłać $4$ jeny, aby wyłączyć lampkę $5$, czyli skrajnie prawą włączoną lampkę. Stan lampek jest reprezentowany przez napis -RBB--.
4. Zapłać $5$ jenów, aby wybrać lampkę $3$ i przełączyć ją na kolor zielony. Stan lampek jest reprezentowany przez napis -RGB--.

Ponieważ nie da się uzyskać powtórzenia RGB płacąc mniej niż $16$ jenów, wypisujemy $16$.

Ten przykład spełnia ograniczenia podzadań $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Na przykład po wykonaniu $3$ operacji w poniższy sposób ciąg kolorów włączonych lampek staje się powtórzeniem RGB. Wyłączona lampka jest oznaczona znakiem -.

1. Zapłać $1$ jena, aby wybrać lampkę $2$ i przełączyć ją na kolor zielony. Stan lampek jest reprezentowany przez napis BGG.
2. Zapłać $1$ jena, aby wybrać lampkę $3$ i przełączyć ją na kolor niebieski. Stan lampek jest reprezentowany przez napis BGB.
3. Zapłać $1$ jena, aby wybrać lampkę $1$ i przełączyć ją na kolor czerwony. Stan lampek jest reprezentowany przez napis RGB.

Ponieważ nie da się uzyskać powtórzenia RGB płacąc mniej niż $3$ jeny, wypisujemy $3$.

Ten przykład spełnia ograniczenia podzadań $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

Na przykład po wykonaniu $3$ operacji w poniższy sposób ciąg kolorów włączonych lampek staje się powtórzeniem RGB. Wyłączona lampka jest oznaczona znakiem -.

1. Zapłać $9$ jenów, aby wyłączyć lampkę $1$, czyli skrajnie lewą włączoną lampkę. Stan lampek jest reprezentowany przez napis -RB.
2. Zapłać $9$ jenów, aby wyłączyć lampkę $2$, czyli skrajnie lewą włączoną lampkę. Stan lampek jest reprezentowany przez napis --B.
3. Zapłać $9$ jenów, aby wyłączyć lampkę $3$, czyli skrajnie lewą włączoną lampkę. Stan lampek jest reprezentowany przez napis ---.

Ponieważ nie da się uzyskać powtórzenia RGB płacąc mniej niż $27$ jenów, wypisujemy $27$. Zauważ, że przypadek, w którym włączonych jest $0$ lampek, również spełnia warunek.

Ten przykład spełnia ograniczenia podzadań $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Ponieważ ciąg kolorów lampek jest już powtórzeniem RGB, wypisujemy $0$.

Ten przykład spełnia ograniczenia podzadań $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Ten przykład spełnia ograniczenia podzadań $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Ten przykład spełnia ograniczenia podzadań $2, 3, 6$.