Substring appearing twice

Time limit6sMemory limit128 MB

Summary

Given a string and at most K letter replacements, maximize the length of the longest substring that occurs at two different starting positions, allowing overlap.

Level: Hard8 of 10
Topics: String, Binary search, Dynamic programming, String matching
Solved: No attempts yet

Problem

You are given a string $S$ of lowercase English letters.

Define the following value: the length of the longest substring that occurs at two different starting positions in $S$ . The two occurrences may overlap. If no such substring exists, the value is $0$ .

You may replace a letter of $S$ with any other lowercase letter, and you may do this at most $K$ times. After every replacement is made, the value above is computed on the resulting string. Find the largest value you can reach.

Replacements apply to the string itself, once. When the two occurrences overlap, the letters inside the overlap are shared by both occurrences.

Input

The first line contains the integer $K$ ( $0 \le K \le 5000$ ).

The second line contains the string $S$ , made of lowercase English letters only ( $1 \le |S| \le 5000$ ).

Output

Print one integer, the largest value reachable with at most $K$ replacements.

Note

Take $K = 1$ and $S$ equal to abcba. Changing the third letter c to a gives ababa, where the substring aba occurs at position 0 and at position 2. The answer is 3.

Examples3

Example 1
Input
```
1
abcba
```
Expected output
```
3
```
Example 2
Input
```
7
aaaaaaaaaa
```
Expected output
```
9
```
Example 3
Input
```
2
tmirkoxlyzmirkoslav
```
Expected output
```
8
```