В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом. Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова a, ab и aba являются префиксами слова aba. Например, набор слов aba, aa и bac является беспрефиксным кодом, а набор abac, aba, ba нет, поскольку слово aba является префиксом слова abac.
Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор abac, abс, ba является почти беспрефиксным кодом уровня 2, а набор abac, abab, ba нет, поскольку наибольший общий префикс слов abac и abab имеет длину 3.
Очередная задача, которую профессор Дешифро поставил своим лаборантам, заключается в следующем: по заданному набору слов и числу k требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня k. Вам, как младшему лаборанту, поручили написать соответствующую программу.
Выведите одно число
m - максимальное количество слов, которые можно выбрать из заданного набора, чтобы они образовывали почти беспрефиксный код уровня
k.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 2
aba
bacaba
abacaba
baca
abac
caba
|
3 |