Прибирай!

Одного разу Чарлі вирішив почати нове життя, видаливши всі файли у своєму каталозі Завантаження. Це легко зробити за допомогою оболонки 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 *" одразу, тому що спочатку всі чотири файли відповідають порожньому префіксу.