193. Слова, в которые играют люди

Антон очень любит гулять. В перерывах между прогулками он увлекается различными играми со словами. Естественно, от него не могли ускользнуть такие идеальные слова как палиндромы. Палиндром - слово которое одинаково читается как слева направо, так и справа налево. На одной из своих прогулок Антон придумал для себя игру. В этой игре каждый игрок пишет некоторое слово($word$) на листе бумаги. Далее ведущий называет некоторое число($k$). После этого происходит проверка идеальности каждого из слов участников. Идеальностью слова называют некоторое максимальное число($perfect$) при которой в строке $word$ есть не менее $k$ не пересекающихся подстрок-палиндромов длины($perfect$). Победителем признается тот, кто придумал самое идеальное слово.

Антон сразу заметил, что считать идеальность слова не так просто: если не автоматизировать её нахождение, то ему вряд ли удастся уговорить своих друзей поиграть с ним. Так как Антон очень сильно занят своими прогулками, он просит вас помочь ему, чтобы он мог играть со своими друзьями.

В первой строке находится число $k \le |word|$. Во второй строке находится строка $word$ ($|word| \le 10^4$) состоящая из прописных латинских буквы(a-z).

В единственной строке выведите идеальность слова.