Statement is not available in English language
F. Название команды
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во Всеберляндской олимпиаде по программированию могут участвовать команды в составе $$$n$$$ человек. Для участия каждой команде нужно выбрать название.

Участники одной из команд составили название, включающее каждое из их имен, и записали его в строку $$$t$$$ длины $$$m$$$. Однако, такое название получилось слишком длинным! Поэтому они хотят сократить его следующим образом:

  • выбрать префикс строки $$$t$$$ минимальной длины, который включал бы все их имена без пересечений.

Префиксом строки называется строка, полученная удалением нескольких (возможно, нуля) последних символов из исходной строки.

Некоторое множество подстрок входит в строку без пересечений, если никакой символ не принадлежит двум подстрокам одновременно. Например, подстроки «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| \lt m$$$) — имя $$$i$$$-го участника команды ($$$1 \le i \le n$$$). Длина строки $$$s_i$$$ обозначается как $$$|s_i|$$$.

Гарантируется, что сумма значений $$$|s_i|$$$ не превосходит значения $$$m$$$, и в строку $$$t$$$ можно поместить имена всех участников без пересечений.

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

Выведите:

  • Число -1, если название команды невозможно сократить;
  • Иначе длину минимального префикса строки $$$t$$$, в который могут войти имена всех участников без пересечений.
Примеры
Входные данные
4 22
omihaakrisssashaannaaa
kris
miha
sasha
anna
Выходные данные
20
Входные данные
2 16
coolnickgoodalex
nick
alex
Выходные данные
-1
Входные данные
3 7
bababab
a
bab
b
Выходные данные
5