題目描述

有 $N$ 盞燈排成一橫排，由左至右依次編號為 $1$ 到 $N$。每盞燈嘅顏色係紅、綠、藍三者之一。燈嘅顏色由字串 $S$ 表示：當 $S$ 嘅第 $i$ 個字元（$1 \le i \le N$）係 R 嗰陣，燈 $i$ 嘅顏色係紅色；係 G 嗰陣係綠色；係 B 嗰陣係藍色。起初所有燈都係開住嘅。

只要仲有至少 $1$ 盞開住嘅燈，JOI 君就可以按任意順序執行以下 $3$ 種操作任意咁多次（亦可以做 $0$ 次）：

• 畀 $A$ 日圓，將目前開住嘅燈入面最左邊嗰盞熄咗佢。
• 畀 $B$ 日圓，將目前開住嘅燈入面最右邊嗰盞熄咗佢。
• 畀 $C$ 日圓，揀 $1$ 盞目前開住嘅燈，將佢重新較成鍾意嘅顏色。

JOI 君希望由遠處望呢排燈嗰陣呈現出靚靚嘅白色。為咗咁樣，開住嘅燈由左向右望嘅顏色序列必須好似 RGBRGB...RGB 咁樣，係 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-- 表示。

因為無辦法畀少過 $16$ 日圓令開住嘅燈嘅顏色序列變成 RGB 嘅重複，所以輸出 $16$。

呢個樣例滿足子任務 $2, 3, 6$ 嘅限制。

3
BRG
1000000000 1000000000 1

3

例如按以下方式做 $3$ 次操作之後，開住嘅燈嘅顏色序列就會變成 RGB 嘅重複。熄咗嘅燈用 - 表示。

1. 畀 $1$ 日圓，揀燈 $2$ 並將佢重新較成綠色。各盞燈嘅狀態由字串 BGG 表示。
2. 畀 $1$ 日圓，揀燈 $3$ 並將佢重新較成藍色。各盞燈嘅狀態由字串 BGB 表示。
3. 畀 $1$ 日圓，揀燈 $1$ 並將佢重新較成紅色。各盞燈嘅狀態由字串 RGB 表示。

因為無辦法畀少過 $3$ 日圓令開住嘅燈嘅顏色序列變成 RGB 嘅重複，所以輸出 $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$ 熄咗佢。各盞燈嘅狀態由字串 --- 表示。

因為無辦法畀少過 $27$ 日圓令開住嘅燈嘅顏色序列變成 RGB 嘅重複，所以輸出 $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$ 嘅限制。