題目描述

有 $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$ 的限制。