Maximizing Word Occurrences in Partitioned String

You are given a string consisting of lowercase English letters with length at most 200. The string is given in lines, each containing exactly 20 characters. You are also given an integer k and a dictionary of at most 6 words. Your task is to partition the entire string into exactly k contiguous segments such that the total number of dictionary word occurrences in all segments is maximized.

In each segment, you are allowed to count occurrences of dictionary words according to the following rule: occurrences may overlap partially; however, once you select a word occurrence starting at position i (where the occurrence is a substring beginning at that index), the letter at that position cannot be used as the starting letter for any other word occurrence in that segment. In other words, for any index in a segment, you may count at most one occurrence (even if multiple dictionary words match starting at that position). A dictionary word occurrence is considered valid in a segment if the entire word fits within that segment.

Formally, let the concatenated string be denoted by \(S\) of length \(n\) (\(n\le200\)). For each position \(i\) (0-indexed), if there exists a word \(w\) in the dictionary such that \(S[i:i+|w|-1]=w\), then we say index \(i\) is potentially matchable provided that the segment in which it occurs has length at least \(|w|\) from that index onward. If at index \(i\) multiple dictionary words match, then define \(\min\_len[i]\) as the minimum length among all matching words. In a segment covering positions \([L, R]\), an index \(i\) is counted if \(R - i + 1 \ge \min\_len[i].

Your goal is to choose segmentation boundaries to maximize the sum of counts over the k segments.

The answer is the maximum total count achievable.

Note: All formulas are rendered in \(\LaTeX\) format.

inputFormat

The input is given as follows:

Line 1: An integer k, the number of segments.
Line 2: An integer m, the number of words in the dictionary (1 ≤ m ≤ 6).
Next m lines: Each line contains one dictionary word (non-empty string of lowercase letters).
Next line: An integer L, denoting the number of lines of the letter string. The total length of the string is 20 * L.
Next L lines: Each line contains exactly 20 lowercase letters (without spaces).

You must use the entire letter string in order.

outputFormat

Output a single integer, which is the maximum total count of dictionary word occurrences in all segments after an optimal partition into k contiguous segments.

sample

1
2
this
is
1
thisisateststringxyz

3