CF682D.Alyona and Strings

After returned from forest, Alyona started reading a book. She noticed strings s and t, lengths of which are n and m respectively. As usual, reading bored Alyona and she decided to pay her attention to strings s and t, which she considered very similar.

Alyona has her favourite positive integer k and because she is too small, k does not exceed 10. The girl wants now to choose k disjoint non-empty substrings of string s such that these strings appear as disjoint substrings of string t and in the same order as they do in string s. She is also interested in that their length is maximum possible among all variants.

Formally, Alyona wants to find a sequence of k non-empty strings _p_1, _p_2, _p_3, ..., p__k satisfying following conditions:

• s can be represented as concatenation _a_1_p_1_a_2_p_2... a__k__p__k__a__k + 1, where _a_1, _a_2, ..., a__k + 1 is a sequence of arbitrary strings (some of them may be possibly empty);
• t can be represented as concatenation _b_1_p_1_b_2_p_2... b__k__p__k__b__k + 1, where _b_1, _b_2, ..., b__k + 1 is a sequence of arbitrary strings (some of them may be possibly empty);
• sum of the lengths of strings in sequence is maximum possible.

Please help Alyona solve this complicated problem and find at least the sum of the lengths of the strings in a desired sequence.

A substring of a string is a subsequence of consecutive characters of the string.

从森林回来后，Alyona 开始阅读一本书。她注意到两个字符串 $s$ 和 $t$，其长度分别为 $n$ 和 $m$。和往常一样，读书让 Alyona 感到无聊，于是她决定将注意力转向字符串 $s$ 和 $t$，并认为它们非常相似。

Alyona 有一个她最喜爱的正整数 $k$，且由于她年纪尚小，$k$ 不超过 10。现在，她希望从字符串 $s$ 中选出 $k$ 个互不相交的非空子串，使得这些子串也以相同的顺序作为互不相交的子串出现在字符串 $t$ 中。她还希望这些子串的总长度尽可能大。

形式化地说，Alyona 希望找到一个由 $k$ 个非空字符串 $p_1,\,p_2,\,p_3,\,\dots,\,p_k$ 组成的序列，满足以下条件：

• $s$ 可表示为拼接形式 $a_1p_1a_2p_2\ldots a_kp_ka_{k+1}$，其中 $a_1,\,a_2,\,\dots,\,a_{k+1}$ 是一串任意字符串（其中某些可以为空）；
• $t$ 可表示为拼接形式 $b_1p_1b_2p_2\ldots b_kp_kb_{k+1}$，其中 $b_1,\,b_2,\,\dots,\,b_{k+1}$ 是一串任意字符串（其中某些可以为空）；
• 序列中所有字符串的长度之和尽可能大。

请帮助 Alyona 解决这个复杂的问题，并至少求出所求序列中字符串的长度之和。

字符串的一个子串是指该字符串中连续字符组成的子序列。

In the first line of the input three integers n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10) are given — the length of the string s, the length of the string t and Alyona's favourite number respectively.

The second line of the input contains string s, consisting of lowercase English letters.

The third line of the input contains string t, consisting of lowercase English letters.

输入的第一行包含三个整数 $n$、$m$、$k$（$1 ≤ n, m ≤ 1000$，$1 ≤ k ≤ 10$），分别表示字符串 $s$ 的长度、字符串 $t$ 的长度以及 Alyona 最喜欢的数字。

输入的第二行包含字符串 $s$，由小写英文字母组成。

输入的第三行包含字符串 $t$，由小写英文字母组成。

In the only line print the only non-negative integer — the sum of the lengths of the strings in a desired sequence.

It is guaranteed, that at least one desired sequence exists.

在唯一的一行中输出唯一的非负整数——该理想序列中所有字符串长度的总和。

保证至少存在一个理想序列。

The following image describes the answer for the second sample case:

以下图片描述了第二个样例的解答：