תיאור הבעיה

ישנן $N$ נורות המסודרות בשורה אופקית, וממוספרות מ-$1$ עד $N$ משמאל לימין. צבעה של כל נורה הוא אדום, ירוק או כחול. צבעי הנורות מיוצגים על ידי מחרוזת $S$, כאשר צבע הנורה ה-$i$ ($1 \le i \le N$) הוא אדום אם התו ה-$i$ של $S$ הוא R, ירוק אם הוא G, וכחול אם הוא B. בהתחלה כל הנורות דולקות.

כל עוד יש לפחות נורה $1$ דולקת, JOI-kun יכול לבצע את $3$ סוגי הפעולות הבאים בכל סדר ומספר פעמים שירצה (מותר גם לבצע $0$ פעולות):

• לשלם $A$ ין כדי לכבות את הנורה הדולקת השמאלית ביותר.
• לשלם $B$ ין כדי לכבות את הנורה הדולקת הימנית ביותר.
• לשלם $C$ ין כדי לבחור נורה דולקת $1$ ולהדליק אותה מחדש בכל צבע שירצה.

JOI-kun רוצה ששורת הנורות הזו תיראה בצבע לבן יפה כאשר מביטים בה מרחוק. לשם כך, רצף הצבעים של הנורות הדולקות משמאל לימין חייב להיות חזרה של 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$.