Covered Characters Optimization in a String

Given a string \(A\) and \(n\) substrings \(B_1, B_2, \ldots, B_n\) such that each \(B_i\) appears in \(A\) at least once, we want to choose for each \(B_i\) exactly one occurrence in \(A\) (an occurrence is defined by an interval in \(A\) where \(B_i\) appears exactly). These occurrences (which may overlap) cover some characters of \(A\). Your task is to determine two numbers:

• The minimum number of characters of \(A\) that can be covered by the chosen occurrences.
• The maximum number of characters of \(A\) that can be covered by the chosen occurrences.

An occurrence of a substring \(B_i\) is represented as an interval \([l_i, r_i]\) (1-indexed) such that \(A[l_i..r_i] = B_i\). The union of all chosen intervals is the set of characters in \(A\) that are covered. Formally, if the chosen intervals are \(I_1, I_2, \ldots, I_n\) then the covered characters are \[ \bigcup_{i=1}^n I_i, \] and its size is the number of distinct positions in \(A\) that belong to at least one \(I_i\).

Note on the objectives:

1. Minimum Covered: You want to choose for each \(B_i\) an occurrence such that the union of the intervals is as small as possible. Intuitively, you try to “stack” the intervals so that they overlap as much as possible. A useful observation is that if there exists an interval \([x,y]\) of \(A\) such that for every \(B_i\), there is an occurrence completely contained in \([x,y]\), then the union can be at most \(y-x+1\). The answer is the minimum such length over all segments \([x,y]\) of \(A\) that can cover one occurrence for each \(B_i\).
2. Maximum Covered: You want to choose occurrences so that the covered positions are as spread out as possible (i.e. with as little overlapping as possible). In the ideal case, if you can choose disjoint occurrences then the number of covered characters is the sum of the lengths of each \(B_i\); however, you are limited by the positions in \(A\). You must choose for each \(B_i\) one of its intervals where it occurs in \(A\).

Input format: The first line contains the string \(A\). The second line contains an integer \(n\). The following \(n\) lines each contain a substring \(B_i\). It is guaranteed that each \(B_i\) appears in \(A\).

Output format: Output two integers separated by a space, representing the minimum and maximum number of characters covered, respectively.

inputFormat

The input begins with a line containing the string \(A\). The next line contains an integer \(n\). Following that, there are \(n\) lines, each containing one substring \(B_i\) (\(1 \le i \le n\)).

You may assume that \(1 \le |A| \le 100\) and \(1 \le n \le 10\).

outputFormat

Output two integers separated by a space: the minimum number of characters of \(A\) that can be covered by the chosen placements, and the maximum number of characters that can be covered.

sample

ababa
2
aba
bab

4 4