Problem
Max mempunyai dua rentetan s panjang n dan t panjang m ditulis dalam buku notanya, yang terdiri daripada huruf "a"; dan "b" abjad Latin. Selain itu, Max tahu bahawa rentetan t mempunyai bentuk «abab...», iaitu, huruf «a» berada pada kedudukan ganjil rentetan dan huruf — "b".
Tiba-tiba, pada waktu pagi, Max mendapati bahawa seseorang telah mengacaukan rentetannya. Beberapa s telah ditukar kepada "?".
Mari kita panggil urutan kedudukan i, i + 1, ..., i + m - 1 kejadian rentetan t dalam s, jika 1 ≤ ;i ≤ n - m + 1 dan t
1 = s
i, t
2 &thinsp ;= s
i + 1, ..., t
m = s
i + m - 1.
Keindahan rentetan s diukur sebagai bilangan maksimum kejadian tidak bertindih rentetan t di dalamnya. Max boleh menggantikan beberapa "?" di atas" atau "b" (aksara dalam kedudukan yang berbeza boleh digantikan dengan huruf yang berbeza). Max ingin membuat penggantian supaya keindahan rentetan s adalah sebesar mungkin. Daripada semua pilihan ini, dia mahu menggantikan sesedikit mungkin aksara "?". Ketahui berapa banyak penggantian yang perlu dia lakukan.
Input:
Baris pertama mengandungi integer tunggal n (1 ≤ n ≤ 10
5) — panjang tali s.
Baris kedua input mengandungi rentetan s panjang n, hanya terdiri daripada huruf "a"; dan "b" abjad Latin, serta simbol «?».
Baris ketiga mengandungi integer m (1 ≤ m ≤ 10
5) — panjang tali t. Rentetan t itu sendiri mengandungi "a"; dalam kedudukan ganjil, dan "b" pada nombor genap.
Output:
Cetak satu integer — bilangan minimum penggantian yang mesti dibuat oleh Vasya untuk menjadikan keindahan rentetan itu semaksimal mungkin.
Contoh:
| Input |
Output |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Penjelasan:
Dalam contoh pertama, rentetan t adalah dalam bentuk "a". Satu-satunya pilihan optimum — menggantikan semua aksara "?" kepada «a».
Dalam contoh kedua, menggunakan dua penggantian, anda boleh mendapatkan rentetan "aba?aba??". Anda tidak boleh mendapat lebih daripada dua penyertaan.