Description

You are given a string. You may split this string into segments. For example, abcvsdaas can be split as abc|vs|d|aas. You are also given a dictionary. Each segment after splitting must contain at least one word from the dictionary as a substring. What is the maximum number of segments you can obtain?

Input Format

• The first line contains a string.
• The second line contains a positive integer $N$, the number of strings in the dictionary.
• The next $N$ lines each contain a string $A_i$, representing a dictionary string.

Output Format

Output one integer, the maximum number of segments.

asdsd
3
as
sd
ds

2

Hint

Special case: If the original string cannot be split, output $0$.

Constraints: For $20\%$ of the testdata, $1\leq |s| \leq 50, 1\leq n\leq 50$. For $100\%$ of the testdata, $1\leq |A_i| \leq |s|\leq 300, 1\leq N\leq 500$. Here, $|s|, |A_i|$ denote the lengths of string $s$ and $A_i$.

Translated by ChatGPT 5