题目描述

o と x からなる長さ $N$ の文字列 $S$ と、整数 $M,K$ が与えられます。
$S$ には少なくとも $1$ つの x が含まれることが保証されます。

$S$ を $M$ 個連結して得られる長さ $NM$ の文字列を $T$ とします。 $T$ に含まれる x のうち丁度 $K$ 個を選んで o に変えることを考えます。
あなたの目標は、変更後の $T$ に o のみからなるできるだけ長い連続部分文字列が含まれるようにすることです。
o のみからなる連続部分文字列の長さとして達成可能な最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$ $S$

输出格式

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

题目大意

给你一个由 o 和 x 组成的长度为 $N$ 的字符串 $S$，以及整数 $M$ 和 $K$。保证 $S$ 至少包含一个 x。

假设 $T$ 是由 $S$ 复制 $M$ 次而成的长度为 $NM$ 的字符串。考虑将 $T$ 中的 $K$ 个 x 恰好替换为 o。

你的目标是在替换后的 $T$ 中有尽可能长的由 o 组成的连续子串。

找出在替换后由 o 组成的连续子串的最大长度。

10 1 2
ooxxooooox

9

5 3 4
oxxox

8

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

19964887064

提示

制約

• $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$ の連続部分文字列が得られ、これが達成可能な最大値です。