Trong quá luyện tập cho cuộc thi học sinh giỏi sắp tới, Hùng được thầy giáo giao cho thử sức giải bài toán nén xâu kí tự (chỉ gồm các kí tự la tinh in hoa) sau đây.

Phép cộng trên hai xâu ~x~ và ~y~, kí hiệu là ~x + y~, được hiểu là ghép xâu ~y~ liền sau xâu ~x~. Xuất phát từ hai xâu ~u,\,v~ và số nguyên ~k~, xâu ~F_k~ được tạo theo luật sau (còn được gọi là luật tựa Fibonacci):

Ví dụ, với hai xâu ~u =~ AB, ~v =~ C và ~k = 5~ ta có:

Giả sử xâu ~T~ có độ đài ~n~ là xâu được tao theo luật trên từ hai xâu xuất phát ~u_T,\,v_T~ có độ dài tương ứng là ~n_1,\,n_2~. Như vậy, ~v_T~ là xâu gồm ~n_2~ kí tự đầu tiên của xâu ~T~ và ~u_T~ là xâu gồm ~n_1~ kí tự tiếp theo của xâu ~T~. Xâu ~T~ có thể được nén thành bộ ~(u_T,\,v_T,\,n)~ vì từ 3 thông tin ~u_T,\,v_T~ và ~n~ ta có thể khôi phục được xâu ~T~ theo luật trên. Ví dụ xâu ~T =~ CABCCAB có thể được nén thành bộ ~(~AB, C, ~7)~.

Một xâu ~S~ bất kì có độ dài ~m~ cũng có thể được nén theo cách như trên. Với hai số nguyên dương ~m_1,\,m_2\,(m_1 + m_2 \le m)~, gọi ~v_S~ là xâu gồm ~m_2~ kí tự đầu tiên của xâu ~S~ và ~u_S~ là xâu gồm ~m_1~ kí tự tiếp theo trên xâu ~S~. Khi đó, xâu ~S~ có thể được nén thành bộ ~(u_S,\,v_S,\,m)~. Tuy nhiên, từ 3 thông tin ~u_S,\,v_S~ và ~m~ ta có thể không khôi phục được chính xác xâu ~S~. Do đó, người ta đánh giá độ lỗi của phương pháp nén xâu này như sau. Với bộ ~(u_S,\,v_S,\,m)~, tạo xâu ~F_k~ với k nhỏ nhất mà độ dài ~F_k~ lớn hơn hoặc bằng ~m~ theo luật tựa Fibonacci từ hai xâu xuất phát ~F_1 = u_S~, ~F_2 = v_S~. Độ lỗi của việc nén xâu ~S~ được tính bằng số lượng vị trí ~i~ mà ~S[i]~ khác với ~F_k[i]~, trong đó ~S[i]~ và ~F_k[i]~ tương ứng là kí tự thứ ~i~ của xâu ~S~ và xâu ~F_k~ với ~i \le m~.

Ví dụ, với ~m_1 = 2~ và ~m_2 = 1~, xâu ~S =~ CABACC có độ dài ~m = 6~ được nén thành bộ ~(~AB, C, ~6)~, sau đó tạo ra xâu ~F_5 =~ CABCCAB. Khi đó đội lỗi của việc nén xâu ~S~ là ~2~ do có hai kí tự ở các vị trí thứ 4 và thứ 6 của ~S~ và ~F_5~ là khác nhau.

Nhận thấy rằng ~m_2 + m_1~ kí tự đầu tiên của xâu ~S~ ảnh hưởng rất lớn đến độ lỗi của việc nén xâu. Vì vậy, người ta tiến hành thay đổi không quá ~r~ kí tự trong ~m_2 + m_1~ kí tự đầu tiên của xâu ~S~ để biến xâu ~S~ thành xâu ~S^*~ sao cho độ lỗi của việc nén xâu ~S^*~ là nhỏ nhất. Việc thay đổi một kí tự là thay kí tự đó bởi một kí tự khác.

Yêu cầu: Cho các số nguyên ~m,\,m_1,\,m_2,\,r~ và xâu ~S~, hãy tìm cách thay đổi không quá ~r~ kí tự trong ~m_2 + m_1~ kí tự đầu tiên của xâu ~S~ để biến xâu ~S~ thành xâu ~S^*~ sao cho độ lỗi của việc nén xâu ~S^*~ là nhỏ nhất.

Lưu ý: Đọc input, output từ stdin/stdout (không phải từ file như trong đề)

Dữ liệu

Dòng thứ nhất chứa bốn số nguyên cách nhau bởi dấu cách ~m,\,m_1,\,m_2,\,r\,(0 \le r \le m_2 + m_1 \le m)~; Dòng thứ hai chứa xâu ~S~ độ dài ~m~, xâu chỉ gồm các kí tự thuộc tập kí tự chữ cái la tinh in hoa (từ A đến Z).

Kết quả

Ghi ra một số nguyên là độ lỗi nhỏ nhất tìm được.

Ràng buộc

• Có ~30\%~ số test tương ứng ~30\%~ số điểm của bài thỏa mãn điều kiện: ~r = 0;\,m \le 10^3;~
• ~40\%~ số test khác ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~r = m_1 + m_2 \le 10;\,m \le 10^3~ và xâu ~S~ chỉ gồm hai kí tự A và B~;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~m \le 10^5~.

Sample Input

6 2 1 1
CABAAC

Sample Output

1

Giải thích

Trong ví dụ trên, cách thay đổi tối ưu nhất là thay kí tự đầu tiên của xâu ~S~ thành A để nhận được xâu ~S^*~ = AABAAC. Với ~m_1 = 2~ và ~m_2 = 1~, xâu ~S^*~ được nén thành bộ ~(~AB, A, ~6)~, ta tạo ra xâu ~F_5~ = AABAAAB. Khi đó, độ lỗi của việc nén xâu ~S^*~ bằng ~1~ do kí tự ở vị trí thứ 6 của ~S^*~ và ~F_5~ là khác nhau.