题目描述

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

将 $S$ 重复 $M$ 次连接起来得到长度为 $NM$ 的字符串 $T$。你需要将 $T$ 中恰好 $K$ 个 x 替换为 o。
你的目标是使得 $T$ 中连续的 o 组成的子串尽可能长。
找出你能够得到的连续的 o 组成的子串的最大长度。

约束条件

• $N$、$M$ 和 $K$ 是整数。
• $1 \le N \le 3 \times 10^5$
• $1 \le M \le 10^9$
• $1 \le K \le x$，其中 $x$ 是字符串 $T$ 中 x 的数量。
• $S$ 是由 o 和 x 组成、长度为 $N$ 的字符串。
• $S$ 至少包含一个 x。

输入

输入以以下格式从标准输入中给出：

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

输出

输出作为一个整数。

示例输入 1

10 1 2
ooxxooooox

示例输出 1

9

$S=$ ooxxooooox，$T=$ ooxxooooox。
将 $T$ 中第三个和第四个字符的 x 替换为 o，得到 $T=$ ooooooooox。
现在我们有一个由 o 组成、长度为 $9$ 的连续子串，这是可能的最长子串。

示例输入 2

5 3 4
oxxox

示例输出 2

8

$S=$ oxxox，$T=$ oxxoxoxxoxoxxox。
将 $T$ 中第 $5$、$7$、$8$ 和 $10$ 个字符的 x 替换为 o，得到 $T=$ oxxooooooooxxox。
现在我们有一个由 o 组成、长度为 $8$ 的连续子串，这是可能的最长子串。

示例输入 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

示例输出 3

19964887064