Problem
マックスは、長さ n の s と長さ m の t の 2 つの文字列をノートに書き、「a」という文字で構成されていました。と「b」ラテン系のアルファベット。さらに、Max は文字列 t が «abab...» という形式を持っていること、つまり、文字 «a» が文字列の奇数の位置にあり、文字 — が文字列の奇数の位置にあることを認識しています。 "b".
ある朝突然、マックスは誰かが彼女の弦を台無しにしたことに気づきました。一部の s は「?」に変更されています。
位置 i, i + 1, ..., i + m - 1 のシーケンスを s 内の文字列 t の出現と呼びましょう。 ;i ≤ n - m + 1 および t
1 = s
i, t
2 = s
i + 1, ..., t
m = s
i + m - 1.
文字列 s の美しさは、文字列 t が重なっていない最大数として測定されます。 Max は「?」の一部を置き換えることができます。 「あ」にまたは「b」 (異なる位置にある文字は、異なる文字に置き換えることができます)。 Max は、文字列 s の美しさができるだけ大きくなるように置換を行いたいと考えています。これらすべてのオプションの中で、彼女はできるだけ少ない "?" 文字を置き換えたいと考えています。彼女が何回交代しなければならないかを調べてください。
入力:
最初の行には、単一の整数 n (1 ≤ n ≤ 10
5) — が含まれています。文字列の長さ s.
入力の 2 行目には、文字 "a" のみで構成される、長さ n の文字列 s が含まれています。と「b」ラテン アルファベットと記号 «?».
3 行目には、整数 m (1 ≤ m ≤ 10
5) — が含まれています。文字列の長さ t.文字列 t 自体には "a" が含まれています。奇数の位置、および「b」
出力:
単一の整数を出力します —弦の美しさを最大限に引き出すために、ヴァシャが行わなければならない置換の最小数.
例:
<本体>
| 入力 |
出力 |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
説明:
最初の例では、文字列 t の形式は "a" です。唯一の最適なオプション —すべての文字を置き換えます "?" 「a」へ。
2 番目の例では、2 つの置換を使用して、文字列 "aba?aba??" を取得できます。 2 つ以上のエントリを取得することはできません。