从森林回来后,阿廖娜开始读书。她注意到字符串 s 和 t,长度分别为 n 和 m。和往常一样,阅读让阿廖娜感到无聊,她决定把注意力集中在字符串 s 和 t 上,她认为它们非常相似。
Alyona 有她最喜欢的正整数 k,因为她太小,k 不超过 10。女孩现在想要选择字符串 s 的 k 个不相交非空子串,使得这些字符串显示为字符串 t 的不相交子串,并且顺序与它们在字符串 s 中的顺序相同。她还感兴趣的是,它们的长度是所有变体中可能的最大长度。
形式上,Alyona 希望找到满足以下条件的 k 个非空字符串 p1, p2, p3, ..., pk 的序列:
- s 可以表示为串联 a1p1a2p2... akpkak + 1,其中 a1, a2, ..., ak + 1 是任意字符串的序列(其中一些可能为空);
- t 可以表示为串联 b1p1b2p2... bkpkbk + 1,其中 b1, b2, ..., bk + 1 是任意字符串的序列(其中一些可能为空);
- 序列中字符串长度的总和是最大可能的。
请帮助 Alyona 解决这个复杂的问题,并至少找到所需序列中字符串的长度之和。
字符串的子字符串是字符串的连续字符的子序列。
输入
在输入的第一行给出了三个整数 n、m、k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10)——分别是字符串 s 的长度、字符串 t 的长度和 Alyona 最喜欢的数字。
输入的第二行包含字符串 s,由小写英文字母组成。
输入的第三行包含字符串 t,由小写英文字母组成。
输出
在唯一的行中打印唯一的非负整数 - 所需序列中字符串的长度之和。
保证至少存在一个所需的序列。
示例
输入 #1
3 2 2 abc ab
输出 #1
2
输入 #2
9 12 4 bbaaababb abbbabbaaaba
输出 #2
7
注意
下图描述了第二个示例案例的答案: