问题 AA: 晫晫的字符串

内存限制：256 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：32 通过：13

返回比赛提交提交记录

晫晫有两个字符串s和t，其长度分别为n和m。

晫晫有他最喜欢的正整数 k（k 不超过 10）。晫晫现在想要选择字符串 s 的 k 个不相交的连续非空子串，并且这些子串在字符串t中均出现且顺序相同。

形式上，晫晫希望找到满足以下条件的 k 个非空字符串序列 p1，p2，p3,...,pk：

s 可以表示为串联 a₁p₁a₂p₂... a_kp_ka_k+1，其中 a1，a2,...,ak+1 是任意字符串序列（其中一些可能为空）;

t 可以表示为串联 b₁p₁b₂p₂... b_kp_kb_k+1，其中 b1，b2,...,bk+1 是任意字符串序列（其中一些可能为空）;

序列中字符串长度的总和是可能的最大值。

请帮助晫晫解决这个复杂的问题，并至少找到所需序列中字符串长度的总和。

字符串的子字符串是字符串的连续字符的子序列。

输入第一行包括三个整数n,m, k(1≤n,m≤1000,1≤k≤10)分别表示字符串s的长度，字符串t的长度和Alyona最喜欢的数字。

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

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

输出所需序列中字符串长度的总和。题目保证至少存在一个所需的序列。

Examples

Input

3 2 2
abc
ab

Output

Input

9 12 4
bbaaababb
abbbabbaaaba

Output

解释：

下图描述了第二个示例案例的答案：

9 12 4
bbaaababb
abbbabbaaaba