Прибирай!#11134
Одного разу Чарлі вирішив почати нове життя, видаливши всі файли у своєму каталозі Завантаження. Це легко зробити за допомогою оболонки bash! Вона має дві корисні функції: команду "rm", яка видаляє всі файли, передані як аргументи, і шаблони, які замінюються списком файлів, що їм відповідають, перед виконанням команди.
Чарлі виконав "rm *", але отримав повідомлення "Argument list too long". На жаль, після того, як bash замінила "*" на імена всіх файлів у каталозі Завантаження, вона не змогла виконати команду, оскільки аргументів було занадто багато.
Після деяких експериментів Чарлі зрозумів, що може виконати "rm abc*", щоб видалити всі файли з іменами, що починаються на "abc", якщо таких файлів не більше ніж . Якщо більше ніж файлів відповідають цьому шаблону, жоден з них не буде видалено. Звісно, він може замінити "abc" на будь-який рядок.
Допоможіть Чарлі знайти найменшу кількість команд "rm", необхідних для видалення всіх файлів. Припустимо, що він може використовувати команду "rm" лише як "rm <prefix>*", де <prefix> складається з малих літер англійського алфавіту (і може бути порожнім).
Перший рядок містить два цілі числа та — кількість файлів для видалення та максимальну кількість файлів, які можуть бути видалені однією командою "rm" (1 \le n, k \le 3 \cdot 10^5).
Кожен з наступних рядків містить один рядок, що позначає ім'я файлу. Всі імена файлів є унікальними, непорожніми та складаються з малих літер англійського алфавіту. Загальна довжина всіх імен файлів не перевищує 3 \cdot 10^5.
Виведіть одне ціле число — найменшу кількість команд "rm", необхідних для видалення всіх файлів.
Приклад 1
Приклад 2
Приклад 3
У першому прикладі тесту Чарлі може виконати "rm ab*", щоб видалити файли "abc" та "abd", а потім виконати "rm *", щоб видалити файли "a" та "b". Зверніть увагу, що він не може просто виконати "rm *" одразу, тому що спочатку всі чотири файли відповідають порожньому префіксу.