Cool substring#10360
Sign in

Cool substring

1 second
256 megabytes
Medium

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 of length , composed of lowercase Latin letters. He can change up to 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 and (1 \leq n \leq 5 \cdot 10^6, 0 \leq k \leq 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 , which consists of lowercase Latin letters.

Output

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

Examples

Example 1

Loading
Loading

Scoring

  1. ( points): n \leq 100;

  2. ( points): n \leq 3\,000;

  3. ( points): n \leq 100\,000;

  4. ( points): k = 0;

  5. ( points): no additional constraints.