29050번 - Заклинания 다국어

Мэйвис хочет применить очень сильное заклинание, чтобы вернуть Джонатана. У нее есть несколько обычных заклинаний, которые она хочет скрестить, чтобы получить сильное. Все заклинания представляют собой непустые строки из строчных латинских букв. У Мэйвис есть $k$ обычных заклинаний $a_i$. Она также знает заклинание $t$, которое она хочет получить в результате.

Процесс скрещивания происходит следующим образом: изначально у Мэйвис есть пустая строка $s$, Мэйвис производит несколько этапов скрещиваения: во время каждого этапа она выбирает номер обычного заклинания $i$ и делает одно из действий

• $s = s + a_i$ --- строки конкатенируются;
• $s = s \times a_i$ --- строки умножаются: после каждого символа строки $s$ записывается строка $a_i$.

Обратите внимание, что операция $\times{}$ не коммутативна.

В результате скрещивания Мэйвис хочет получить строку $t$. Помогите ей определить, какое минимальное количество этапов потребуется для этого.

В первой строке содержится строка $t$ ($1 \le |t| \le 5 \times 10^4$) --- заклинание, которое хочет получить Мэйвис, в следующей строке находится число $k$ --- количество обычных заклинаний, имеющихся у нее, в следующих $k$ ($1 \le k \le 1000$) строках находятся обычные заклинания $a_i$ ($1 \le |a_i| \le 100$) по одному в строке.

Все строки непустые и состоят из строчных латинских букв.

В единственной строке выведите минимальное количество этапов, которое потребуется Мэйвис для получения строки $t$, либо \text{ ---1}, если это сделать невозможно.