Задача 04G. Идеальное стихотворение ≡

Условие

Лев хочет написать стихотворение для своей девушки. У него есть K строк, которые он бы хотел использовать. Строки ставятся друг за другом так, чтобы между ними была рифма. Считается, что между двумя строками есть рифма, если последние Т символов этих строк совпадают. Лев считает, что чем больше рифмы в поэзии, тем лучше. Поэтому он решил составить стихотворение так, чтобы все строки в нем рифмовались друг с другом.

Определите максимальное количество строк с одинаковыми T буквами на конце. Гарантируется, что как минимум две такие строки существуют.

Формат входных данных

Первая строка входных данных содержит 2 целых числа: K  — количество строк, которые имеются у Льва и T  — требуемое количество совпадающих символов. Далее следует K строк, из которых нужно выбрать строки для стихотворения.

Формат выходных данных

Выходные данные должны содержать единственное число — максимально возможное количество строк стихотворения.

Ограничения

1 ≤ K, T ≤ 1000

Примеры тестов

8 2
If I ever were to lose you
I'd surely lose myself
Everything I have found dear
I've not found by myself
Try and sometimes you'll succeed
To make this man of me
All my stolen missing parts
I've no need for anymore

2

5 2
And both that morning equally lay
In leaves no step had trodden black
Oh I kept the first for another day
Yet knowing how way leads on to way
I doubted if I should ever come back

3