두 번 나타나는 부분 문자열

영어 소문자로 이루어진 문자열 $S$가 있다.

먼저 다음 값을 정의한다. $S$ 안에서 서로 다른 두 시작 위치에 나타나는 부분 문자열 중 가장 긴 것의 길이다. 두 등장 구간은 겹쳐도 된다. 그런 부분 문자열이 하나도 없으면 이 값은 $0$이다.

이제 $S$의 글자를 다른 소문자로 바꿀 수 있고, 바꾸기는 최대 $K$번까지 할 수 있다. 바꾸기를 모두 끝낸 문자열에서 위 값을 계산한다. 이 값을 가장 크게 만들었을 때의 값을 구하여라.

바꾸기는 문자열에 한 번만 적용된다. 두 등장 구간이 겹치면 겹친 자리의 글자는 두 등장에 함께 쓰인다.

첫째 줄에 정수 $K$가 주어진다. ($0 \le K \le 5000$)

둘째 줄에 영어 소문자로만 이루어진 문자열 $S$가 주어진다. ($1 \le |S| \le 5000$)

최대 $K$번의 변경으로 얻을 수 있는 가장 큰 값을 정수 하나로 출력한다.

$K = 1$이고 $S$가 abcba인 경우를 보자. 세 번째 글자 c를 a로 바꾸면 문자열은 ababa가 되고, 부분 문자열 aba가 0번 위치와 2번 위치에 나타난다. 답은 3이다.