Однажды Чарли решил начать новую жизнь, удалив все файлы в своей папке Загрузки. Это легко сделать с помощью оболочки 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 2aabcabdb
2
4 2dcaba
2
5 3pleaseremoveallthesefiles
3
В первом примере теста Чарли может выполнить команду "rm ab*" для удаления файлов "abc" и "abd", а затем выполнить команду "rm *" для удаления файлов "a" и "b". Обратите внимание, что он не может просто запустить команду "rm *" сразу, потому что изначально все четыре файла соответствуют пустому префиксу.