Problem
Max có hai chuỗi s độ dài n và t độ dài m được viết trong sổ tay của cô ấy, bao gồm các chữ cái "a"; và B" bảng chữ cái Latinh. Hơn nữa, Max biết rằng chuỗi t có dạng «abab...», nghĩa là chữ cái «a» nằm ở các vị trí lẻ của chuỗi và chữ cái — "b".
Đột nhiên, vào buổi sáng, Max phát hiện ra rằng ai đó đã làm hỏng chuỗi s của cô ấy. Một số chữ s đã được đổi thành "?".
Hãy gọi dãy vị trí i, i + 1, ..., i + m - 1 là sự xuất hiện của chuỗi t trong s, nếu 1 ≤&thinsp ;i ≤ n - m + 1 và t
1 = s
i, t
2 &thinsp ;= s
i + 1, ..., t
m = s
i + m - 1.
Độ đẹp của xâu s được đo bằng số lần xuất hiện không trùng lặp lớn nhất của xâu t trong đó. Max có thể thay thế một số dấu "?" trên "một" hoặc "b" (các ký tự ở các vị trí khác nhau có thể được thay thế bằng các chữ cái khác nhau). Max muốn thay thế sao cho độ đẹp của chuỗi s càng lớn càng tốt. Trong tất cả các tùy chọn này, cô ấy muốn thay thế càng ít ký tự "?" càng tốt. Tìm xem cô ấy phải thực hiện bao nhiêu lần thay người.
Đầu vào:
Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 10
5) — chiều dài chuỗi s.
Dòng thứ hai chứa một xâu s độ dài n, chỉ chứa các chữ cái "a"; và B" bảng chữ cái Latinh, cũng như các ký hiệu «?».
Dòng thứ ba chứa số nguyên m (1 ≤ m ≤ 10
5) — chiều dài chuỗi t. Bản thân chuỗi t chứa "a"; ở các vị trí lẻ và "b" về số chẵn.
Đầu ra:
In một số nguyên duy nhất — số lần thay thế ít nhất mà Vasya phải thực hiện để vẻ đẹp của chuỗi s là tối đa có thể.
Ví dụ:
| Đầu vào |
Đầu ra |
5
bb?a?
1 |
2 |
9
b??a b?ng ???
3 |
2 |
Giải thích:
Trong ví dụ đầu tiên, chuỗi t có dạng "a". Tùy chọn tối ưu duy nhất — thay thế tất cả các ký tự "?" đến «a».
Trong ví dụ thứ hai, sử dụng hai phép thay thế, bạn có thể nhận được chuỗi "aba?aba??". Bạn không thể nhận được nhiều hơn hai mục.