Во Всеберляндской олимпиаде по программированию могут участвовать команды в составе $$$n$$$ человек. Для участия каждой команде нужно выбрать название.
Участники одной из команд составили название, включающее каждое из их имен, и записали его в строку $$$t$$$ длины $$$m$$$. Однако, такое название получилось слишком длинным! Поэтому они хотят сократить его следующим образом:
Префиксом строки называется строка, полученная удалением нескольких (возможно, нуля) последних символов из исходной строки.
Некоторое множество подстрок входит в строку без пересечений, если никакой символ не принадлежит двум подстрокам одновременно. Например, подстроки «a» и «bc» входят в строку «ababc» без пересечений, а подстроки «aba» и «abc» — нет.
Если название команды возможно сократить — выведите длину минимального подходящего префикса.
Первая строка входных данных содержит два целых числа: $$$n$$$ ($$$2 \le n \le 8$$$) — количество участников в команде, и $$$m$$$ ($$$2 \le m \le 2 \cdot 10^5$$$) —длину названия, составленного командой.
Вторая строка входных данных содержит строку $$$t$$$, состоящую из строчных латинских букв — название, составленное командой.
Далее следуют $$$n$$$ строк, каждая из которых содержит строку $$$s_i$$$, состоящую из строчных латинских букв ($$$1 \le |s_i| < m$$$) — имя $$$i$$$-го участника команды ($$$1 \le i \le n$$$). Длина строки $$$s_i$$$ обозначается как $$$|s_i|$$$.
Гарантируется, что сумма значений $$$|s_i|$$$ не превосходит значения $$$m$$$, и в строку $$$t$$$ можно поместить имена всех участников без пересечений.
Выведите:
4 22omihaakrisssashaannaaakrismihasashaanna
20
2 16coolnickgoodalexnickalex
-1
3 7babababababb
5