Description

There are $n$ lamps in a row. Some lamps are on, and some are off. Keke wants the lamps to be alternating. He defines the ugliness of a row of lamps as the number of lamps in the longest consecutive segment that are all on or all off. Keke can press switches at most $k$ times. Each operation toggles the state of one lamp: if it was on, it becomes off; otherwise, it becomes on. Given the current states of the lamps, find the minimal ugliness after the operations.

Input Format

The first line contains two integers $n, k$.

The second line is a string of length $n$ consisting of two characters: N and F. Here, N means the lamp is on, and F means the lamp is off.

Output Format

Output the minimal ugliness.

8 1
NNNFFNNN

3

Hint

$30\%$ of the testdata: $1\le k \le n\le 20$.

$50\%$ of the testdata: $1\le k \le n\le 300$.

Another $15\%$ of the testdata: $1\le k \le n\le 10^5$, and the string is all N or all F.

$100\%$ of the testdata: $1\le k \le n\le 10^5$.

This problem includes hack testdata.

Translated by ChatGPT 5