(JSOIII means JSOI 2.)

It is already 7 months since the intense battle in JSOI, but HarryBOB and cl_lmc still cannot forget the exciting moments in the match.

One night, HarryBOB had a dream that he was given a $1\cdot N$ grid, where every cell is filled with either red or blue. No cells are colourless.
As a JSOI contestant, of course he wants his colour (red) to appear more. Therefore, he thinks a continuous segment in the grid is Beautiful if and only if the number of red cells is larger or equal to the number of blue cells.

As this is in HarryBOB's dream, he can actually change the colour of cells. But as he will wake up soon, he can only change colour for at most $K$ cells.

You are given the original colours of the cells and the integer $K$. Find the mininum possible positive value of $M$ such that after changing the colour, all continuous segments of length at least $M$ is Beautiful.

Input

The first line consists of two integers $N$ and $K$. The second line consists of a string $s$ of length $N$ indicating the original colours of the grid. If the $i$-th cell is red, $s_i=$ R, or else $s_i=$ B.

Output

Output a single integer indicating the minimum possible positive value of $M$.

Subtasks

For all cases,
$0\le K \le 10^6, 1 \le N \le 10^6, K \le N$
$s_i=$R or B for $1\le i \le N$

Subtask 1 ($10$ pts): $N\le 100, K=0$
Subtask 2 ($20$ pts): $N\le 5000, K=0$
Subtask 3 ($30$ pts): $K=0$
Subtask 4 ($20$ pts): $N\le 100$
Subtask 5 ($10$ pts): $N\le 5000$
Subtask 6 ($10$ pts): No additional constraints