P1026 [NOIP 2001 Senior] Count the Number of Words

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.

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.

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

- 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