โจทย์ปัญหา

มีหลอดไฟ $N$ ดวงเรียงกันเป็นแนวนอน โดยมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N$ ตามลำดับจากซ้ายไปขวา สีของหลอดไฟแต่ละดวงคือสีแดง สีเขียว หรือสีน้ำเงิน สีของหลอดไฟแทนด้วยสตริง $S$ โดยที่สีของหลอดไฟดวงที่ $i$ ($1 \le i \le N$) จะเป็นสีแดงเมื่ออักขระตัวที่ $i$ ของ $S$ คือ R เป็นสีเขียวเมื่อคือ G และเป็นสีน้ำเงินเมื่อคือ B ในตอนแรกหลอดไฟทุกดวงเปิดอยู่

ตราบใดที่มีหลอดไฟที่เปิดอยู่อย่างน้อย $1$ ดวง โจอิคุงสามารถดำเนินการ $3$ ประเภทต่อไปนี้ในลำดับใดก็ได้และกี่ครั้งก็ได้ (สามารถดำเนินการ $0$ ครั้งก็ได้):

• จ่าย $A$ เยน เพื่อปิดหลอดไฟดวงที่อยู่ซ้ายสุดในบรรดาหลอดไฟที่เปิดอยู่
• จ่าย $B$ เยน เพื่อปิดหลอดไฟดวงที่อยู่ขวาสุดในบรรดาหลอดไฟที่เปิดอยู่
• จ่าย $C$ เยน เพื่อเลือกหลอดไฟที่เปิดอยู่ $1$ ดวง แล้วเปลี่ยนให้เปิดเป็นสีใดก็ได้ที่ต้องการ

โจอิคุงต้องการให้แถวของหลอดไฟนี้ดูเป็นสีขาวที่สวยงามเมื่อมองจากระยะไกล ในการทำเช่นนั้น ลำดับสีของหลอดไฟที่เปิดอยู่เมื่อมองจากซ้ายไปขวาจะต้องเป็นการซ้ำกันของ 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$ เป็นจำนวนเต็ม

งานย่อย (Subtasks)

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$

ข้อมูลส่งออก

แสดงจำนวนเงินขั้นต่ำที่ต้องใช้เพื่อทำให้ลำดับสีของหลอดไฟที่เปิดอยู่เป็นการซ้ำกันของ RGB ใน $1$ บรรทัด โดยไม่ต้องระบุหน่วย (เยน)

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

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$