C. Уборка!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
4 2
a
abc
abd
b
Выходные данные
2
Входные данные
4 2
d
c
ab
a
Выходные данные
2
Входные данные
5 3
please
remove
all
these
files
Выходные данные
3
Примечание

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