Cool line

Cossack Vus considers a string to be cool if it satisfies the following conditions:

1. All characters at even indices are identical.

2. All characters at odd indices are identical.

For instance, the strings 'wow' and 'ftftf' are cool, whereas 'cabab' and 'abcd' are not.

Cossack Vus has a string $s$ of length $n$, composed of lowercase Latin letters. He can change up to $k$ characters in the string to create a cool substring of the maximum possible length. Your task is to determine this maximum length.

Input

The first line contains two integers $n$ and $k$ ($1\le n\le 5\cdot 10^6$, $0\le k\le 5\cdot 10^6$) — the length of the string and the maximum number of characters Cossack Vus is allowed to change.

The second line contains the string $s$, which consists of $n$ lowercase Latin letters.

Output

Output a single integer — the maximum length of a cool substring that Cossack Vus can achieve.

Examples

Scoring

1. ($7$ points): $n\le 100$;

2. ($14$ points): $n\le 3000$;

3. ($33$ points): $n\le 100000$;

4. ($23$ points): $k=0$;

5. ($23$ points): no additional constraints.