Məsələlər
Reduction
Reduction
Дана строка \textbf{S} и список \textbf{M}, состоящий из \textbf{N} слов, каждое из которых длины \textbf{L}. За одну операцию можно выбрать некоторую подстроку строки \textbf{S}, если такая встречается в качестве слова в списке \textbf{M}, и вырезать из строки \textbf{S}. После чего оставшиеся части строки \textbf{S}, если такие есть, склеиваются.
Определить, за какое минимальное количество операций можно уничтожить всю строку \textbf{S}. Гарантируется, что это можно сделать.
\InputFile
В первой строке слово \textbf{S}. Во второй строке целое число \textbf{N} --- количество слов в списке. Далее \textbf{N} строк, в каждой из которых по одному слову из списка \textbf{M}. Все слова состоят только из строчных латинских букв.
\OutputFile
Одно число --- минимальное количество операций, необходимое для уничтожения строки \textbf{S}.
\textbf{Ограничения}
\textbf{1} ≤ \textbf{|S|} ≤ \textbf{100}
\textbf{1} ≤ \textbf{N} ≤ \textbf{100}
\textbf{1} ≤ \textbf{|M_i|} ≤ \textbf{100}
\textbf{1} ≤ \textbf{L} ≤ \textbf{|S|}
Giriş verilənləri #1
abacabada 4 aba aca ada abb
Çıxış verilənləri #1
3