{"problem":{"name":"E. Maximum Questions","description":{"content":"Vasya wrote down two strings _s_ of length _n_ and _t_ of length _m_ consisting of small English letters '_a_' and '_b_'. What is more, he knows that string _t_ has a form \"_abab..._\", namely there ar","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF900E"},"statements":[{"statement_type":"Markdown","content":"Vasya wrote down two strings _s_ of length _n_ and _t_ of length _m_ consisting of small English letters '_a_' and '_b_'. What is more, he knows that string _t_ has a form \"_abab..._\", namely there are letters '_a_' on odd positions and letters '_b_' on even positions.\n\nSuddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string _s_ were replaced by character '_?_'.\n\nLet's call a sequence of positions _i_, _i_ + 1, ..., _i_ + _m_ - 1 as _occurrence_ of string _t_ in _s_, if 1 ≤ _i_ ≤ _n_ - _m_ + 1 and _t_1 = _s__i_, _t_2 = _s__i_ + 1, ..., _t__m_ = _s__i_ + _m_ - 1.\n\nThe boy defines the _beauty_ of the string _s_ as maximum number of disjoint occurrences of string _t_ in _s_. Vasya can replace some letters '_?_' with '_a_' or '_b_' (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string _s_ is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the length of _s_.\n\nThe second line contains the string _s_ of length _n_. It contains small English letters '_a_', '_b_' and characters '_?_' only.\n\nThe third line contains a single integer _m_ (1 ≤ _m_ ≤ 105) — the length of _t_. The string _t_ contains letters '_a_' on odd positions and '_b_' on even positions.\n\n## Output\n\nPrint the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string _s_ the maximum possible.\n\n[samples]\n\n## Note\n\nIn the first sample string _t_ has a form '_a_'. The only optimal option is to replace all characters '_?_' by '_a_'.\n\nIn the second sample using two replacements we can make string equal to \"_**aba**?**aba**??_\". It is impossible to get more than two occurrences.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Vasya 写下了两个字符串 #cf_span[s]（长度为 #cf_span[n]）和 #cf_span[t]（长度为 #cf_span[m]），均由小写英文字母 '_a_' 和 '_b_' 组成。此外，他知道字符串 #cf_span[t] 的形式为 \"_abab..._\"，即奇数位置为字母 '_a_'，偶数位置为字母 '_b_'。\n\n一天早晨，Vasya 发现他的字符串被破坏了：字符串 #cf_span[s] 中的一些字母被替换成了字符 '_?_'。\n\n我们称位置序列 #cf_span[i, i + 1, ..., i + m - 1] 为字符串 #cf_span[t] 在 #cf_span[s] 中的一个 _出现_，当且仅当 #cf_span[1 ≤ i ≤ n - m + 1] 且 #cf_span[t1 = si, t2 = si + 1, ..., tm = si + m - 1]。\n\n男孩定义字符串 #cf_span[s] 的 _美丽值_ 为 #cf_span[s] 中互不重叠的 #cf_span[t] 出现的最大数量。Vasya 可以将某些 '_?_' 替换为 '_a_' 或 '_b_'（不同位置可以替换为不同字母）。Vasya 希望进行一些替换，使得字符串 #cf_span[s] 的美丽值尽可能大。在所有能使美丽值最大的方案中，他希望选择替换次数最少的那个。请找出他需要进行的最少替换次数。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）— 字符串 #cf_span[s] 的长度。\n\n第二行包含长度为 #cf_span[n] 的字符串 #cf_span[s]，仅包含小写英文字母 '_a_'、'_b_' 和字符 '_?_'。\n\n第三行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 105]）— 字符串 #cf_span[t] 的长度。字符串 #cf_span[t] 在奇数位置为 '_a_'，在偶数位置为 '_b_'。\n\n请输出一个整数 —— Vasya 为使字符串 #cf_span[s] 的美丽值达到最大可能值所需进行的最少替换次数。\n\n在第一个样例中，字符串 #cf_span[t] 的形式为 '_a_'。唯一最优的选择是将所有 '_?_' 替换为 '_a_'。\n\n在第二个样例中，通过两次替换，我们可以使字符串变为 \"_*aba*?*aba*??_\"。不可能获得超过两个出现。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）— 字符串 #cf_span[s] 的长度。\n\n第二行包含长度为 #cf_span[n] 的字符串 #cf_span[s]，仅包含小写英文字母 '_a_'、'_b_' 和字符 '_?_'。\n\n第三行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 105]）— 字符串 #cf_span[t] 的长度。字符串 #cf_span[t] 在奇数位置为 '_a_'，在偶数位置为 '_b_'。\n\n## Output\n\n请输出一个整数 —— Vasya 为使字符串 #cf_span[s] 的美丽值达到最大可能值所需进行的最少替换次数。\n\n[samples]\n\n## Note\n\n在第一个样例中，字符串 #cf_span[t] 的形式为 '_a_'。唯一最优的选择是将所有 '_?_' 替换为 '_a_'。\n\n在第二个样例中，通过两次替换，我们可以使字符串变为 \"_*aba*?*aba*??_\"。不可能获得超过两个出现。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq m \\leq n \\leq 10^5 $.  \nLet $ s \\in \\{a, b, ?\\}^n $ be the corrupted string.  \nLet $ t \\in \\{a, b\\}^m $ be the target string defined by:  \n$$\nt_i = \n\\begin{cases}\na & \\text{if } i \\text{ is odd}, \\\\\nb & \\text{if } i \\text{ is even}.\n\\end{cases}\n$$\n\nAn *occurrence* at position $ i $ (for $ 1 \\leq i \\leq n - m + 1 $) is a substring $ s[i:i+m-1] $ such that $ s[i+j-1] = t_j $ for all $ j \\in \\{1, \\dots, m\\} $, after replacing all $ ? $ in $ s $ with $ a $ or $ b $.  \nTwo occurrences are *disjoint* if their intervals $[i, i+m-1]$ and $[i', i'+m-1]$ do not overlap.\n\nThe *beauty* of $ s $ is the maximum number of disjoint occurrences of $ t $ that can be formed by replacing $ ? $ with $ a $ or $ b $.\n\n**Constraints**  \n1. $ s $ contains only characters from $ \\{a, b, ?\\} $.  \n2. $ t $ is fixed as alternating $ a, b, a, b, \\dots $ of length $ m $.  \n3. Replacements may only change $ ? $ to $ a $ or $ b $.  \n\n**Objective**  \nFind the *minimum number of replacements* (i.e., number of $ ? $ changed) required to achieve the *maximum possible beauty* (i.e., maximum number of disjoint occurrences of $ t $).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF900E","tags":["data structures","dp","strings"],"sample_group":[["5\nbb?a?\n1","2"],["9\nab??ab???\n3","2"]],"created_at":"2026-03-03 11:00:39"}}