Maximum Extractions

Given a string s consisting of lowercase English letters and a list of target words, determine the maximum number of times all target words can be simultaneously extracted from s based solely on character frequencies.

For each target word t, let \(f_t(c)\) denote the frequency of character \(c\) in t and let \(F(c)\) denote the frequency of \(c\) in s. The number of times word t can be extracted is given by \[ \min_{c \in t} \left\lfloor \frac{F(c)}{f_t(c)} \right\rfloor \] The answer is the minimum extraction count among all target words.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a string s consisting of lowercase English letters.
• The second line contains an integer n, the number of target words.
• The following n lines each contain one target word.

outputFormat

Output a single integer to standard output (stdout), representing the maximum number of times all target words can be simultaneously extracted from the given string.

abacabacaba
3
ab
ca
ac

2