Đề bài
Có $N$ bóng đèn được xếp thành một hàng ngang, được đánh số từ $1$ đến $N$ theo thứ tự từ trái sang phải. Màu của mỗi bóng đèn là đỏ, lục hoặc lam. Màu của các bóng đèn được biểu diễn bởi một xâu $S$, trong đó màu của bóng đèn $i$ ($1 \le i \le N$) là đỏ khi ký tự thứ $i$ của $S$ là R, lục khi là G, và lam khi là B. Ban đầu tất cả các bóng đèn đều đang sáng.
Chừng nào còn ít nhất $1$ bóng đèn đang sáng, JOI-kun có thể thực hiện $3$ loại thao tác sau theo thứ tự tùy ý với số lần tùy ý (cũng có thể thực hiện $0$ lần):
- Trả $A$ yên để tắt bóng đèn đang sáng nằm ở ngoài cùng bên trái.
- Trả $B$ yên để tắt bóng đèn đang sáng nằm ở ngoài cùng bên phải.
- Trả $C$ yên để chọn $1$ bóng đèn đang sáng và bật lại nó thành màu tùy thích.
JOI-kun muốn khi nhìn hàng đèn này từ xa thì nó sẽ có màu trắng đẹp mắt. Để được như vậy, dãy màu của các bóng đèn đang sáng khi nhìn từ trái sang phải phải là sự lặp lại của RGB (đỏ, lục, lam) như RGBRGB...RGB. Tuy nhiên, trường hợp có $0$ bóng đèn đang sáng cũng được coi là sự lặp lại của RGB. Lưu ý rằng các dãy màu như GBRGBR hay RGBRG không thỏa mãn điều kiện.
Cho thông tin về các bóng đèn và số tiền cần thiết cho các thao tác, hãy viết chương trình tìm số tiền tối thiểu cần thiết để biến dãy màu của các bóng đèn đang sáng thành sự lặp lại của RGB.
Giới hạn
- $1 \le N \le 200\,000$.
- $S$ là xâu có độ dài $N$.
- Mỗi ký tự của $S$ là
R,GhoặcB. - $1 \le A \le 10^9$.
- $1 \le B \le 10^9$.
- $1 \le C \le 10^9$.
- $N, A, B, C$ là các số nguyên.
Subtask
- ($4$ điểm) $N = 3$.
- ($22$ điểm) $N \le 300$.
- ($19$ điểm) $N \le 10\,000$.
- ($9$ điểm) $N$ là bội của $3$, $A = 10^9$, $B = 10^9$, $C = 1$.
- ($10$ điểm) $A = 10^9$, $B = 10^9$, $C = 1$.
- ($36$ điểm) Không có giới hạn bổ sung.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau: $N$ $S$ $A \ B \ C$
Kết quả
In ra trên $1$ dòng số tiền tối thiểu cần thiết để biến dãy màu của các bóng đèn đang sáng thành sự lặp lại của RGB (bỏ qua đơn vị yên).
Ví dụ
6
GRBBRG
3 4 516Ví dụ, khi thực hiện $4$ thao tác như sau, dãy màu của các bóng đèn đang sáng sẽ trở thành sự lặp lại của RGB. Bóng đèn đã tắt được biểu diễn bởi -.
- Trả $3$ yên để tắt bóng đèn $1$ đang sáng nằm ở ngoài cùng bên trái. Trạng thái của các bóng đèn được biểu diễn bởi xâu
-RBBRG. - Trả $4$ yên để tắt bóng đèn $6$ đang sáng nằm ở ngoài cùng bên phải. Trạng thái của các bóng đèn được biểu diễn bởi xâu
-RBBR-. - Trả $4$ yên để tắt bóng đèn $5$ đang sáng nằm ở ngoài cùng bên phải. Trạng thái của các bóng đèn được biểu diễn bởi xâu
-RBB--. - Trả $5$ yên để chọn bóng đèn $3$ và bật lại thành màu lục. Trạng thái của các bóng đèn được biểu diễn bởi xâu
-RGB--.
Vì không thể trả ít hơn $16$ yên để làm cho dãy màu của các bóng đèn đang sáng thành sự lặp lại của RGB, nên in ra $16$.
Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 6$.
3
BRG
1000000000 1000000000 13Ví dụ, khi thực hiện $3$ thao tác như sau, dãy màu của các bóng đèn đang sáng sẽ trở thành sự lặp lại của RGB. Bóng đèn đã tắt được biểu diễn bởi -.
- Trả $1$ yên để chọn bóng đèn $2$ và bật lại thành màu lục. Trạng thái của các bóng đèn được biểu diễn bởi xâu
BGG. - Trả $1$ yên để chọn bóng đèn $3$ và bật lại thành màu lam. Trạng thái của các bóng đèn được biểu diễn bởi xâu
BGB. - Trả $1$ yên để chọn bóng đèn $1$ và bật lại thành màu đỏ. Trạng thái của các bóng đèn được biểu diễn bởi xâu
RGB.
Vì không thể trả ít hơn $3$ yên để làm cho dãy màu của các bóng đèn đang sáng thành sự lặp lại của RGB, nên in ra $3$.
Ví dụ này thỏa mãn các giới hạn của Subtask $1, 2, 3, 4, 5, 6$.
3
GRB
9 11 1427Ví dụ, khi thực hiện $3$ thao tác như sau, dãy màu của các bóng đèn đang sáng sẽ trở thành sự lặp lại của RGB. Bóng đèn đã tắt được biểu diễn bởi -.
- Trả $9$ yên để tắt bóng đèn $1$ đang sáng nằm ở ngoài cùng bên trái. Trạng thái của các bóng đèn được biểu diễn bởi xâu
-RB. - Trả $9$ yên để tắt bóng đèn $2$ đang sáng nằm ở ngoài cùng bên trái. Trạng thái của các bóng đèn được biểu diễn bởi xâu
--B. - Trả $9$ yên để tắt bóng đèn $3$ đang sáng nằm ở ngoài cùng bên trái. Trạng thái của các bóng đèn được biểu diễn bởi xâu
---.
Vì không thể trả ít hơn $27$ yên để làm cho dãy màu của các bóng đèn đang sáng thành sự lặp lại của RGB, nên in ra $27$. Lưu ý rằng trường hợp có $0$ bóng đèn đang sáng cũng thỏa mãn điều kiện.
Ví dụ này thỏa mãn các giới hạn của Subtask $1, 2, 3, 6$.
9
RGBRGBRGB
1000000000 1000000000 10Vì dãy màu của các bóng đèn đã là sự lặp lại của RGB, nên in ra $0$.
Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 4, 5, 6$.
20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 12000000008Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 5, 6$.
23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 71067122910107224827Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3, 6$.