← 返回题目列表

Codeforces · 682/D

D. 阿廖娜和弦乐

中文机器翻译题面 查看原题

从森林回来后,阿廖娜开始读书。她注意到字符串 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

注意

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