Назва ресторану

Limits: 2 sec., 256 MiB

Відвідавши різні заклади харчування в Таїланді, Дракон вирішив відкрити свій ресторан, як то кажуть, з рисом і креветками.

Перше завдання для юного ресторатора — придумати назву закладу. Оскільки заклад буде тайським, то й назва повинна бути відповідною. Для цього на допомогу прийшли його нові друзі (тайці, тайки та ін.) — вони порекомендували йому як назву ресторану рядок \(s\) (ходять чутки, що саме так їхньою мовою пишеться число 47).

Та Дракон не був би Драконом, якби не його дивні забобони. Він каже, що ресторан буде успішним і принесе йому багато грошей тоді і тільки тоді, коли в його назві будуть хоча б два входження деякого однакового підрядка, які не перетинаються. Ще він хоче, щоб довжина цього підрядка повинна бути не меншою ніж \(k\).

Дракон хоче вставити в назву \(s\) якомога меншу кількість символів так, щоб вона стала успішною. Допоможіть йому в цьому і знайдіть цю кількість.

Input

У першому рядку задано одне ціле число \(k\) — мінімальна довжина підрядка, яка повинна зустрічатись в назві хоча б два рази.

У другому рядку задано рядок \(s\), який складається лише з маленьких латинських символів.

Output

У єдиному рядку виведіть одне ціле число — мінімальну кількість символів так, щоб назва ресторану стала успішною.

Constraints

\(1 \le |s|, k \le 50\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 haaaa	1

Input (stdin) сopy	Output (stdout) сopy
4 pakapaka	0

Notes

У першому прикладі можна використати haahaa як назву ресторану.

У другому прикладі можна використати pakapaka як назву ресторану.