Công ty JOI nổi tiếng với những "phát minh kỳ lạ". Gần đây, công ty đã phát triển một trình soạn thảo văn bản mang tên "Just Odd Editor".

Trong trình soạn thảo này, ta có thể nhập một xâu ký tự bằng cách thực hiện nhiều lần các thao tác dưới đây. Gọi \(X\) là xâu đang hiển thị trên màn hình và \(Y\) là xâu được lưu trong bộ nhớ tạm. Ban đầu, cả \(X\) và \(Y\) đều là xâu rỗng.

• Thao tác A: Thêm một ký tự vào cuối xâu. Cụ thể, chọn một ký tự \(c\) rồi thay \(X\) bằng \(X+c\).
• Thao tác B: Chọn toàn bộ các ký tự và cắt chúng. Cụ thể, thay \(Y\) bằng \(X\), sau đó đặt \(X\) thành xâu rỗng.
• Thao tác C: Dán xâu trong bộ nhớ tạm vào cuối xâu. Cụ thể, thay \(X\) bằng \(X+Y\).

Với các ký tự hoặc xâu \(x,y\), ký hiệu \(x+y\) là xâu thu được bằng cách nối \(x\) rồi đến \(y\). Thực hiện một lần thao tác A, B, C lần lượt tốn \(A\), \(B\), \(C\) đơn vị thời gian.

Bạn đã cài đặt Just Odd Editor và muốn nhập xâu \(S\) có độ dài \(N\) nhanh nhất có thể. Hãy thực hiện các thao tác sao cho xâu trên màn hình trở thành \(S\) trong thời gian ngắn nhất.

Viết chương trình nhận độ dài \(N\), xâu \(S\) và thời gian thực hiện mỗi thao tác, rồi tính thời gian ít nhất cần để nhập xâu \(S\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau:

N
S
A
B
C

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn, chứa thời gian ít nhất cần để nhập xâu \(S\).

Ràng buộc

• \(1\le N\le 2\,500\).
• \(S\) là xâu độ dài \(N\), chỉ gồm các chữ cái tiếng Anh thường từ a đến z.
• \(1\le A\le 1\,000\,000\,000=10^9\).
• \(1\le B\le 1\,000\,000\,000=10^9\).
• \(1\le C\le 1\,000\,000\,000=10^9\).
• \(N,A,B,C\) đều là số nguyên.

Phân nhóm

1. \(1\) điểm: \(N=3\).
2. \(5\) điểm: Mọi ký tự của \(S\) đều là a.
3. \(14\) điểm: \(N\le 30\).
4. \(10\) điểm: \(N\le 200\).
5. \(32\) điểm: \(N\le 1\,000\).
6. \(38\) điểm: Không có ràng buộc bổ sung.

Ví dụ

11
mississippi
10
5
2

88

16
aaaaaaaaaaaaaaaa
1
1
1

9

18
aababbbababbbaabbb
1000000000
100000
10000000

8060200000

Nguồn

JOI 2021/2022 Spring Training Camp, Contest 2, do Japanese Committee for the International Olympiad in Informatics (JCIOI) công bố. Bản dịch tiếng Việt được chuyển ngữ từ đề chính thức và phát hành theo giấy phép CC BY-SA 4.0.