Cutting#4595
You are given a string and a list consisting of words. In one operation, you may choose a substring of if it is present as a word in the list , and remove it from . The remaining parts of the string , if any, are concatenated together.
Determine the minimal number of operations required to erase the entire string . It is guaranteed that this can be done.
The first line contains the word . The second line contains the integer , the number of words in the list. The following lines each contain a word from . All words consist of lowercase Latin letters only.
Output one integer: the minimal number of operations required to erase the entire string .
Limits
1 \leq |S| \leq 100
1 \leq N \leq 100
1 \leq |M_i| \leq 100
Example 1