5. Sharadmaker

Умеете придумывать ребусы и шарады? Отлично. Вам придётся научить этому ремеслу компьютер.

Рассмотрим самый простой тип шарад. Слово, которое надо "зашарадить", составляют из нескольких слов, из которых могут быть вычеркнуты некоторые буквы. Например, ШАРАДА - это, например ШАР без вычёркиваний и ПАНДА без первой и третьей буквы, а РЕБУС - это, к примеру, РЕЯ без последней буквы и БРУС без второй. Порядок букв менять нельзя!

Программа, которую вам предстоит написать, получает слово, которое следует зашарадить, количество слов в базе и сами эти слова. Программа должна собрать слово из наименьшего количества слагаемых из базы. При этом количество вычёркиваемых букв не имеет значения, и одно слово можно использовать многократно (КУСТ можно собрать из трёх слагаемых - трёх экземпляров слова СТУК, если в базе нет иных вариантов). Вывести программа должна минимальное количество слов-слагаемых, из которых можно собрать заданное слово.

Входные данные. В первой строке - слово, которое нужно составить из слов базы с вычеркнутыми буквами. В следующей строке - натуральное число N, не превышающее 1000 - количество слов в базе. В следующих N строках слова базы по одному в строке. Все слова состоят только из строчных букв латиницы, длина исходного слова и слов базы не более 50 символов.

Выходные данные. Одно целое число, минимальное возможное количество слагаемых из базы, из которых можно составить заданное слово. Если слово составить невозможно, програма должна вывести -1.

Пример. При вводе следующих данных
october
6
spring
outumn
winter
pocket
cat
cobra
программа должна вывести 3: такой результат можно получить, использовав слова pOCeT, cOBra и wintER.