P3269 [JLOI2016] String Coverage

String $A$ has $N$ substrings $B_1,B_2,...,B_n$. If we place each of these $n$ substrings at exactly one position where it occurs in $A$ (substrings may overlap), then some characters in $A$ will be covered by these $N$ substrings. Find the minimum and maximum possible numbers of covered characters in $A$.

The first line contains a positive integer $T$, the number of test cases. It is guaranteed that $T \le 10$. Then the $T$ test cases follow. For each test case: - The first line contains a string of lowercase letters, the main string $A$. - The second line contains an integer $N$, the number of substrings. - The next $N$ lines each contain a string of lowercase letters, describing a substring. It is guaranteed that every substring occurs in the main string.

Output $T$ lines, one for each test case. Each line contains two integers $Minans$ and $Maxans$, the minimum and maximum numbers of characters that can be covered, respectively.

Constraints: $|A| \le 10000$, $N \le 4$, substring length $\le 10000$. Translated by ChatGPT 5