E. Помочь Хиасату
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хиасат недавно зарегистрировал новый аккаут на сайте NeckoForces и, как только его друзья об этом узнали, каждый из них захотел, чтобы его имя было названием хендла профиля Хиасата.

К счастью для Хиасата, он может менять свой профиль в некоторые моменты времени. Также он знает моменты времени, когда его друзья будут заходить на его страницу. Формально, дана последовательность событий двух видов:

  • $$$1$$$ — Хиасат может поменять свой хендл.
  • $$$2$$$ $$$s$$$ — друг $$$s$$$ посещает профиль Хиасата.

Друг $$$s$$$ будет счастлив, если каждый раз, когда он посетит страницу Хиасата, его хендл будет равен $$$s$$$.

Хиасат просит вас помочь ему, выясните наибольшее количество счастливых друзей, которого можно добиться.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^5, 1 \le m \le 40$$$) — количество событий и количество друзей.

Затем следуют $$$n$$$ строк, задающих событие одно из двух видов:

  • $$$1$$$ — Хиасат может поменять свой хендл.
  • $$$2$$$ $$$s$$$ — друг $$$s$$$ ($$$1 \le |s| \le 40$$$) посещает профиль Хиасата.

Гарантируется, что имя каждого друга состоит только из строчных латинских букв.

Гарантируется, что первое событие обязательно первого типа, и что каждый друг посетит профиль Хиасата хотя бы один раз.

Выходные данные

Выведите одно целое число — наибольшее число счастливых друзей.

Примеры
Входные данные
5 3
1
2 motarack
2 mike
1
2 light
Выходные данные
2
Входные данные
4 3
1
2 alice
2 bob
2 tanyaromanova
Выходные данные
1
Примечание

В первом примере, оптимально поменять хендл на «motarack» в первом событие и на «light» в четвёртом. Таким образом, «motarack» и «light» будут счастливы, а «mike» — нет.

Во втором примере можно выбрать «alice», «bob» или «tanyaromanova», и ровно этот друг и будет счастлив.