题目描述

JOI 君和 IOI 君决定养一只狗。经过讨论，他们决定给狗取一个满足以下所有条件的名字：

1. 名字必须仅包含大写字母和小写字母；
2. JOI 君最喜欢的字符串是长度为 $N$ 的字符串 $S$，名字必须包含 $S$ 作为子序列；
3. IOI 君最喜欢的字符串是长度为 $M$ 的字符串 $T$，名字必须包含 $T$ 作为子序列；
4. 名字中任意两个相同的字符之间必须间隔至少 $K$ 个其他字符。

以上的所有条件区分大小写，例如，我们将 A 和 a 视为不同的字符。

一个字符串的子序列定义为删除其中若干个字符（可以为 $0$ 个）形成的字符串。例如该字符串为 algorithm，那么 ai 和 lgtm 是它的子序列，而 joi 和 logarithm 不是。

由于他们都认为名称越短越好，所以他们决定选用满足上述四个条件的且最短的名字。

给定字符串 $S,T$ 和整数 $K$，请你求出满足条件的名字的最短长度。

输入格式

第一行输入三个整数 $N,M,K$。

第二行输入一个字符串 $S$。

第三行输入一个字符串 $T$。

输出格式

输出一行一个整数表示最小长度。

输入输出样例 #1

10 10 0
hottokeiki
hottokeiki

10

输入输出样例 #2

10 10 1
hottokeiki
hottokeiki

11

输入输出样例 #3

10 10 3
hottokeiki
hottokeiki

15

输入输出样例 #4

6 9 0
Jouhou
Orinpikku

14

输入输出样例 #5

9 7 1
CoMMiTTee
TeRRaCe

15

输入输出样例 #6

6 8 2
JOIIOI
JOIGEGOI

9

说明/提示

【样例解释 #1】

字符串 hottokeiki 满足条件。可以证明，不存在长度更小的字符串满足条件，故答案为 $10$。

该样例满足子任务 $1,3,4,7,8$ 的限制。

【样例解释 #2】

相较于上一个样例，仅有 $K$ 的值发生变化。

在该样例中，上一个样例的输出 hottokeiki 不满足第四个条件（任意两个相同的字符之间必须间隔至少 $K$ 个其他字符），因为两个 t 中没有其他字符。

而字符串 hotNtokeiki 满足条件，可以证明，不存在长度更小的字符串满足条件，故答案为 $11$。

该样例满足子任务 $2,3,5,6,7,8$ 的限制。

【样例解释 #3】

相较于前两个样例，仅有 $K$ 的值发生变化。

在该样例中，上一个样例的输出 hotNtokeiki 不满足第四个条件（任意两个相同的字符之间必须间隔至少 $K$ 个其他字符），因为两个 t 之间仅有 $1$ 个字符，两个 k 之间仅有 $2$ 个字符，两个 i 之间仅有 $1$ 个字符。

而字符串 hotarutokeiyuki 满足条件，可以证明，不存在长度更小的字符串满足条件，故答案为 $15$。

该样例满足子任务 $3,8$ 的限制。

【样例解释 #4】

字符串 OJouhorinpikku 满足条件。可以证明，不存在长度更小的字符串满足条件，故答案为 $14$。

请注意上面的条件区分大小写，因此诸如 jouhorinpikku（长度为 $13$）这样的字符串不符合条件。

该样例满足子任务 $4,7,8$ 的限制。

【样例解释 #5】

字符串 CoMaMiTeRTeRaCe 是长度最小且满足条件的字符串，故答案为 $15$。

该样例满足子任务 $5,6,7,8$ 的限制。

【样例解释 #6】

字符串 JOIGEIGOI 是长度最小且满足条件的字符串，故答案为 $9$。

该样例满足子任务 $7,8$ 的限制。

【数据范围】

• $1\le N,M\le 500$；
• $0\le K\le 3$；
• $S,T$ 中仅包含大写字母和小写字母。

【子任务】

1. （$2$ 分）$S=T$，$K=0$；
2. （$7$ 分）$S=T$，$K=1$；
3. （$16$ 分）$S=T$；
4. （$17$ 分）$K=0$；
5. （$13$ 分）$K=1$，$N,M\le 25$；
6. （$15$ 分）$K=1$；
7. （$20$ 分）$K\le 2$；
8. （$10$ 分）无附加条件。