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

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

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

Выведите:

- Число -1, если название команды невозможно сократить;
- Иначе длину минимального префикса строки $$$t$$$, в который могут войти имена всех участников без пересечений.

Примеры

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

    4 22omihaakrisssashaannaaakrismihasashaanna

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

    20

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

    2 16coolnickgoodalexnickalex

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

    -1

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

    3 7babababababb

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

    5