Splitting a String

Byeongchan has two strings A and B. He thinks the two strings look alike, so he picks K pairwise non-overlapping substrings of A and writes them as $p_1, p_2, \ldots, p_K$ in the order they appear in A. He calls the collection of those strings P. The same substrings must also appear in B, pairwise non-overlapping and in the same order.

P satisfies the following conditions.

1. P has exactly K strings, and every string has length at least 1.
2. String A can be written as $a_1 p_1 a_2 p_2 \cdots a_K p_K a_{K+1}$. Here each of $a_1, a_2, \ldots, a_{K+1}$ is an arbitrary string and may have length 0.
3. String B can be written as $b_1 p_1 b_2 p_2 \cdots b_K p_K b_{K+1}$. Here each of $b_1, b_2, \ldots, b_{K+1}$ is an arbitrary string and may have length 0.
4. PL is the sum of the lengths of all strings in P.

Byeongchan wants the largest possible PL. For example, if A is "bbaaababb", B is "abbbabbaaaba", and K is 4, then P = {"bba", "aa", "b", "a"} makes PL as large as possible, and PL is 7.

The first line contains three integers N, M, K separated by spaces ($1 \le N, M \le 1000$, $1 \le K \le 10$). N is the length of string A, M is the length of string B, and K is the number of strings in P. The second line contains string A, and the third line contains string B. Both strings consist only of the 26 lowercase English letters.

Print the largest PL on the first line. No input is given for which a valid P does not exist.