Trong thời kỳ Chiến tranh Lạnh, Liên Xô sử dụng máy bay cảnh báo sớm và chỉ huy trên không A-50 Mainstay để phát hiện, theo dõi và phân loại các mục tiêu trên không.

Trong một chuyến bay, hệ thống radar của A-50 thu được một chuỗi tín hiệu gồm n ký tự. Mỗi ký tự biểu diễn một loại tín hiệu khác nhau.

Chuỗi tín hiệu được ký hiệu là:

S = s₁s₂...sₙ

Trong đó mỗi sᵢ là một chữ cái thường từ 'a' đến 'z'.

Do ảnh hưởng của nhiễu, một số tín hiệu có thể không đáng tin cậy. Kỹ thuật viên có thể loại bỏ một số ký tự khỏi chuỗi, nhưng không được thay đổi thứ tự của các ký tự còn lại.

Mỗi ký tự sᵢ có hai đại lượng gắn với nó:

• Chi phí năng lượng cᵢ: nếu giữ lại ký tự sᵢ, hệ thống phải tốn cᵢ đơn vị năng lượng.
• Độ tin cậy aᵢ: nếu giữ lại ký tự sᵢ, hệ thống nhận được aᵢ điểm tin cậy.

Tuy nhiên, hệ thống giải mã của A-50 có một quy tắc:

Ví dụ:

• abca là hợp lệ.
• abcba là hợp lệ.
• aabb không hợp lệ.
• abccba không hợp lệ.

Ngoài ra, nếu giữ lại hai ký tự liên tiếp trong chuỗi mới nhưng giữa chúng có d ký tự đã bị loại bỏ trong chuỗi ban đầu, hệ thống phải sử dụng thêm d đơn vị năng lượng để xử lý nhiễu.

Cụ thể, nếu các vị trí được giữ lại là:

i₁ < i₂ < ... < iₖ

thì tổng năng lượng cần sử dụng là:

Máy bay có tối đa \(m\) đơn vị năng lượng.

Hãy tìm tổng độ tin cậy lớn nhất có thể thu được (tức \(a_{i_1} + a_{i_2} + ... + a_{i_k}\)) mà không vượt quá giới hạn năng lượng \(m\).

Nếu không giữ lại được ký tự nào, in ra 0.

(ảnh A-50 Mainstay)

Input

• Dòng đầu tiên chứa hai số nguyên n và m.
• Dòng thứ hai chứa xâu S gồm n ký tự thường từ 'a' đến 'z'.
• Dòng thứ ba chứa n số nguyên c₁, c₂, ..., cₙ — chi phí năng lượng để giữ từng ký tự.
• Dòng thứ tư chứa n số nguyên a₁, a₂, ..., aₙ — độ tin cậy của từng ký tự.

Output

• In ra một số nguyên duy nhất là tổng độ tin cậy lớn nhất có thể đạt được.

Example

7 10
aabacba
2 3 1 4 2 3 1
6 8 5 9 7 4 10

31

6 8
aaabca
2 2 3 1 2 2
5 9 8 7 6 10

32

Ràng buộc

• \(1 \le n \le 2000\)
• \(1 \le m \le 10^5\)
• \(1 \le c_i \le 10^5\)
• \(1 \le a_i \le 10^5\)
• S chỉ gồm các chữ cái thường từ 'a' đến 'z'.

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le n \le 20,\ 1 \le m \le 100\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le n \le 200,\ 1 \le m \le 5000\).
• Subtask \(3\) (\(50\%\) điểm): \(1 \le n \le 2000,\ 1 \le m \le 10^5\).