Description

You are given a string of lowercase English letters with length at most $200$ (the string is provided as $20$ letters per line, and each line has exactly $20$ letters). You must split this string into $k$ contiguous parts so that the total number of words contained in all parts is maximized.

Words in a part may partially overlap. After selecting one word, its first letter cannot be used again. For example, the string this can contain both this and is, but if this is selected, then th cannot be included.

The set of words comes from a given dictionary of at most $6$ words.

Output the maximum count.

Input Format

The input consists of multiple test cases. For each test case:

• The first line contains two positive integers $p, k$. Here $p$ is the number of lines of the string, and $k$ is the number of parts to split into.
• The next $p$ lines each contain exactly $20$ characters.
• The next line contains a positive integer $s$, the number of dictionary words.
• The next $s$ lines each contain one word.

Output Format

For each test case, output one integer: the corresponding result.

1 3
thisisabookyouareaoh
4
is
a
ok
sab

7

Hint

• Constraints: For $100\%$ of the testdata, $2 \le k \le 40$, $1 \le s \le 6$.
• Sample explanation: A valid partition is this / isabookyoua / reaoh.
• Source: NOIP 2001 Senior, Problem 3.

Translated by ChatGPT 5