Уборка!

Чарли решил начать новую жизнь, удалив все файлы в своём каталоге Загрузки. Это легко сделать с помощью оболочки bash! У неё есть две полезные функции: команда "rm", которая удаляет все файлы, переданные в качестве аргументов, и шаблоны, которые заменяются списком файлов, соответствующих им, перед выполнением команды.

Чарли запустил "rm *", но получил ответ "Argument list too long". К сожалению, после того как bash заменил "*" на имена всех файлов в каталоге Загрузки, команда не смогла выполниться из-за слишком большого количества аргументов.

После некоторых экспериментов Чарли понял, что он может выполнить "rm abc*", чтобы удалить все файлы с именами, начинающимися на "abc", если таких файлов не больше $k$. Если более $k$ файлов соответствуют этому шаблону, ни один из них не будет удалён. Конечно, он может заменить "abc" на любую строку.

Помогите Чарли найти минимальное количество команд "rm", необходимых для удаления всех файлов. Предположим, что он может использовать команду "rm" только в виде "rm <prefix>*", где <prefix> состоит из строчных английских букв (и может быть пустым).

Входные данные

Первая строка содержит два целых числа $n$ и $k$ — количество файлов для удаления и максимальное количество файлов, которые могут быть удалены одной командой "rm" ($1\le n,k\le 3\cdot 10^5$).

Каждая из следующих $n$ строк содержит одну строку, обозначающую имя файла. Все имена файлов различны, не пусты и состоят из строчных английских букв. Общая длина всех имён файлов не превышает $3\cdot 10^5$.

Выходные данные

Выведите одно целое число — минимальное количество команд "rm", необходимых для удаления всех файлов.

Примеры

Примечание

В первом примере теста Чарли может выполнить "rm ab*", чтобы удалить файлы "abc" и "abd", а затем выполнить "rm *", чтобы удалить файлы "a" и "b". Обратите внимание, что он не может сразу запустить "rm *", потому что изначально все четыре файла соответствуют пустому префиксу.