Reduction#4610
You are given string and list , consisting of words, each has length . During an operation you may choose substring of string , if it can be found as word in list , and cut it out of string . Then the remaining parts of string are merged, if there are any.
Determine minimal amount of operations required to erase whole string . It is guaranteed that it can be done.
The first line has word . Second line contains integer , that is amount of words in the list. It is followed by lines listing words from . All words consist of lowercase latin letters only.
Output an integer, that is minimal number of operations required to erase whole string .
Limits
1 \le |S| \le 100
1 \le N \le 100
1 \le |M_i| \le 100
1 \le L \le |S|
Example 1