Lát sân chống ma

Cho một sân vườn dạng dải $1\times N$ ô. Mỗi ô là đất (kí hiệu .) hoặc đá (kí hiệu #). Số ô đá không vượt quá $50$.

Bạn cần lát sân bằng ba loại gạch:

• Loại 1: kích thước $1\times 1$, chỉ đặt được trên một ô đất ., mang giá trị $G_1$.
• Loại 2: kích thước $1\times 2$, chỉ đặt được trên hai ô đất liên tiếp .., mang giá trị $G_2$.
• Loại 3: kích thước $1\times 3$, chỉ đặt được trên ba ô liên tiếp theo thứ tự đất–đá–đất .#., mang giá trị $G_3$.

Các viên gạch không được chồng lên nhau (mỗi ô được phủ bởi nhiều nhất một viên), và số viên gạch loại 1 không vượt quá $K$. Số viên gạch loại 2 và loại 3 không bị giới hạn. Bạn không bắt buộc phải lát hết các ô.

Hãy tìm tổng giá trị lớn nhất có thể thu được.

Dữ liệu vào

Dòng đầu chứa năm số nguyên $N$, $K$, $G_1$, $G_2$, $G_3$.

Dòng thứ hai chứa một xâu độ dài $N$ gồm các kí tự . và # mô tả sân vườn.

Dữ liệu ra

In ra một số nguyên — tổng giá trị lớn nhất.

Ràng buộc

• $1\le N\le {10}^5$
• $0\le K\le N$
• $0\le G_1,G_2,G_3\le 1000$
• Số kí tự # trong xâu không vượt quá $50$.

Ví dụ