Problemstellung

Es gibt $N$ Lichter, die in einer horizontalen Reihe angeordnet und von links nach rechts von $1$ bis $N$ nummeriert sind. Die Farbe jedes Lichts ist Rot, Grün oder Blau. Die Farben der Lichter werden durch eine Zeichenkette $S$ dargestellt, wobei die Farbe von Licht $i$ ($1 \le i \le N$) Rot ist, wenn das $i$-te Zeichen von $S$ R ist, Grün, wenn es G ist, und Blau, wenn es B ist. Anfangs leuchten alle Lichter.

Solange mindestens $1$ Licht leuchtet, kann JOI-kun die folgenden $3$ Arten von Operationen in beliebiger Reihenfolge beliebig oft ausführen (es ist auch erlaubt, $0$ Operationen auszuführen):

• Zahle $A$ Yen, um das am weitesten links stehende leuchtende Licht auszuschalten.
• Zahle $B$ Yen, um das am weitesten rechts stehende leuchtende Licht auszuschalten.
• Zahle $C$ Yen, um $1$ leuchtendes Licht auszuwählen und es in einer beliebigen Farbe neu leuchten zu lassen.

JOI-kun möchte, dass diese Lichterreihe aus der Ferne betrachtet in einem schönen Weiß erscheint. Dafür muss die Farbfolge der leuchtenden Lichter von links nach rechts gesehen eine Wiederholung von RGB (Rot, Grün, Blau) wie RGBRGB...RGB sein. Beachten Sie, dass auch der Fall, in dem $0$ Lichter leuchten, als Wiederholung von RGB gilt. Beachten Sie außerdem, dass Farbfolgen wie GBRGBR oder RGBRG die Bedingung nicht erfüllen.

Schreiben Sie anhand der Informationen über die Lichter und die Kosten für die Operationen ein Programm, das den minimalen Geldbetrag ermittelt, der erforderlich ist, um die Farbfolge der leuchtenden Lichter zu einer Wiederholung von RGB zu machen.

Einschränkungen

• $1 \le N \le 200\,000$.
• $S$ ist eine Zeichenkette der Länge $N$.
• Jedes Zeichen von $S$ ist R, G oder B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ sind ganze Zahlen.

Teilaufgaben

1. ($4$ Punkte) $N = 3$.
2. ($22$ Punkte) $N \le 300$.
3. ($19$ Punkte) $N \le 10\,000$.
4. ($9$ Punkte) $N$ ist ein Vielfaches von $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
5. ($10$ Punkte) $A = 10^9$, $B = 10^9$, $C = 1$.
6. ($36$ Punkte) Keine zusätzlichen Einschränkungen.

Eingabe

Die Eingabe erfolgt im folgenden Format: $N$ $S$ $A \ B \ C$

Ausgabe

Geben Sie den minimalen Geldbetrag, der erforderlich ist, um die Farbfolge der leuchtenden Lichter zu einer Wiederholung von RGB zu machen, ohne Einheit (Yen) in $1$ Zeile aus.

Beispiele

6
GRBBRG
3 4 5

16

Wenn beispielsweise $4$ Operationen wie folgt ausgeführt werden, wird die Farbfolge der leuchtenden Lichter zu einer Wiederholung von RGB. Ein ausgeschaltetes Licht wird durch - dargestellt.

1. Zahle $3$ Yen, um Licht $1$ auszuschalten, das am weitesten links leuchtet. Der Zustand der Lichter wird durch die Zeichenkette -RBBRG dargestellt.
2. Zahle $4$ Yen, um Licht $6$ auszuschalten, das am weitesten rechts leuchtet. Der Zustand der Lichter wird durch die Zeichenkette -RBBR- dargestellt.
3. Zahle $4$ Yen, um Licht $5$ auszuschalten, das am weitesten rechts leuchtet. Der Zustand der Lichter wird durch die Zeichenkette -RBB-- dargestellt.
4. Zahle $5$ Yen, um Licht $3$ auszuwählen und es grün leuchten zu lassen. Der Zustand der Lichter wird durch die Zeichenkette -RGB-- dargestellt.

Da es unmöglich ist, mit weniger als $16$ Yen eine Wiederholung von RGB zu erreichen, wird $16$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

Wenn beispielsweise $3$ Operationen wie folgt ausgeführt werden, wird die Farbfolge der leuchtenden Lichter zu einer Wiederholung von RGB. Ein ausgeschaltetes Licht wird durch - dargestellt.

1. Zahle $1$ Yen, um Licht $2$ auszuwählen und es grün leuchten zu lassen. Der Zustand der Lichter wird durch die Zeichenkette BGG dargestellt.
2. Zahle $1$ Yen, um Licht $3$ auszuwählen und es blau leuchten zu lassen. Der Zustand der Lichter wird durch die Zeichenkette BGB dargestellt.
3. Zahle $1$ Yen, um Licht $1$ auszuwählen und es rot leuchten zu lassen. Der Zustand der Lichter wird durch die Zeichenkette RGB dargestellt.

Da es unmöglich ist, mit weniger als $3$ Yen eine Wiederholung von RGB zu erreichen, wird $3$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

Wenn beispielsweise $3$ Operationen wie folgt ausgeführt werden, wird die Farbfolge der leuchtenden Lichter zu einer Wiederholung von RGB. Ein ausgeschaltetes Licht wird durch - dargestellt.

1. Zahle $9$ Yen, um Licht $1$ auszuschalten, das am weitesten links leuchtet. Der Zustand der Lichter wird durch die Zeichenkette -RB dargestellt.
2. Zahle $9$ Yen, um Licht $2$ auszuschalten, das am weitesten links leuchtet. Der Zustand der Lichter wird durch die Zeichenkette --B dargestellt.
3. Zahle $9$ Yen, um Licht $3$ auszuschalten, das am weitesten links leuchtet. Der Zustand der Lichter wird durch die Zeichenkette --- dargestellt.

Da es unmöglich ist, mit weniger als $27$ Yen eine Wiederholung von RGB zu erreichen, wird $27$ ausgegeben. Beachten Sie, dass auch der Fall, in dem $0$ Lichter leuchten, die Bedingung erfüllt.

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

Da die Farbfolge der Lichter bereits eine Wiederholung von RGB ist, wird $0$ ausgegeben.

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

Dieses Eingabebeispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3, 6$.