题目描述

给定一个长度为$n$字符串$S$，你可以选择$k$个位置，将这$k$个位置替换成你想要的任何字符。 你需要最大化替换之后，新的串$S$中最少出现两次的连续子串的长度（两次出现可以重合）。

输入格式

第一行一个非负整数$k$代表最多修改次数。 第二行一个字符串$S$。

输出格式

输出出现两次连续子串的最大长度。

样例输入

2 tmirkoxlyzmirkoslav

样例输出

8

数据范围和约定

对于所有测试点,$k \le n \le 3000$

subtask1(20pts),$n \le 30$

subtask2(20pts),$n \le 500$

subtask3(10pts),$k=0$

subtask4(10pts),$k=1$

subtask5(40pts),无特殊限制