AT_abc300_f [ABC300F] More Holidays

[problemUrl]: https://atcoder.jp/contests/abc300/tasks/abc300_f `o` と `x` からなる長さ $ N $ の文字列 $ S $ と、整数 $ M,K $ が与えられます。 $ S $ には少なくとも $ 1 $ つの `x` が含まれることが保証されます。 $ S $ を $ M $ 個連結して得られる長さ $ NM $ の文字列を $ T $ とします。 $ T $ に含まれる `x` のうち丁度 $ K $ 個を選んで `o` に変えることを考えます。 あなたの目標は、変更後の $ T $ に `o` のみからなるできるだけ長い連続部分文字列が含まれるようにすることです。 `o` のみからなる連続部分文字列の長さとして達成可能な最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ S $

答えを整数として出力せよ。

### 制約 - $ N,M,K $ は整数 - $ 1\ \le\ N\ \le\ 3\ \times\ 10^5 $ - $ 1\ \le\ M\ \le\ 10^9 $ - $ x $ を文字列 $ T $ に含まれる `x` の総数としたとき、 $ 1\ \le\ K\ \le\ x $ - $ S $ は `o` と `x` からなる長さ $ N $ の文字列 - $ S $ には少なくとも $ 1 $ つの `x` が含まれる ### Sample Explanation 1 $ S= $ `ooxxooooox` 、 $ T= $ `ooxxooooox` です。 $ 3 $ 文字目と $ 4 $ 文字目の `x` を `o` に変更することにより、変更後の $ T= $ `ooooooooox` となります。 このとき `o` のみからなる長さ $ 9 $ の連続部分文字列が得られ、これが達成可能な最大値です。 ### Sample Explanation 2 $ S= $ `oxxox` 、 $ T= $ `oxxoxoxxoxoxxox` です。 $ 5,7,8,10 $ 文字目の `x` を `o` に変更することにより、変更後の $ T= $ `oxxooooooooxxox` となります。 このとき `o` のみからなる長さ $ 8 $ の連続部分文字列が得られ、これが達成可能な最大値です。