Problem
مکس دو رشته s به طول n و t به طول m در دفترش نوشته بود که از حروف "a" تشکیل شده بود. و "ب" الفبای لاتین. علاوه بر این، مکس می داند که رشته t شکل «abab...» دارد، یعنی حرف «a» روی موقعیت های فرد رشته قرار دارد و حرف — "ب".
ناگهان، در صبح، مکس متوجه شد که کسی سیم های او را به هم ریخته است. برخی از s ها به "?" تغییر کرده اند.
بیایید دنباله موقعیت‌های i, i + 1, ..., i + m - 1 را یک وقوع رشته t در s، اگر 1 ≤ ;i ≤ n - m + 1 و t
1 = s
i, t
2 &thinsp ;= s
i + 1، ...، t
m = s
i + m - 1.
زیبایی رشته s به عنوان حداکثر تعداد رخدادهای غیر همپوشانی رشته t در آن اندازه گیری می شود. حداکثر می تواند جایگزین برخی از "?" روی "الف" یا "ب" (کاراکترها در موقعیت های مختلف را می توان با حروف مختلف جایگزین کرد). مکس می خواهد تعویض هایی انجام دهد تا زیبایی رشته s تا حد امکان زیاد باشد. از بین همه این گزینه‌ها، او می‌خواهد تا جایی که ممکن است کاراکترهای «؟» را جایگزین کند. ببینید او باید چند تعویض انجام دهد.
ورودی:
خط اول شامل یک عدد صحیح n (1 ≤ n ≤ 10
5) — طول رشته s.
خط دوم ورودی شامل یک رشته s به طول n است که فقط از حروف "a" تشکیل شده است. و "ب" الفبای لاتین و همچنین نمادهای «?».
خط سوم شامل عدد صحیح m (1 ≤ m ≤ 10
5) — طول رشته t. خود رشته t حاوی "a" است. در موقعیت های فرد، و "b" روی اعداد زوج.
خروجی:
چاپ یک عدد صحیح — حداقل تعداد تعویضی که واسیا باید انجام دهد تا زیبایی سیم به حداکثر ممکن برسد.
مثال:
<بدن>
| ورودی |
خروجی |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
توضیحات:
در مثال اول، رشته t به شکل "a" است. تنها گزینه بهینه — جایگزین همه کاراکترهای "?" به «a».
در مثال دوم، با استفاده از دو جایگزین، می توانید رشته "aba?aba??" را دریافت کنید. شما نمی توانید بیش از دو ورودی دریافت کنید.