该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

• 名字必须仅包含大写字母和小写字母；
• 小明最喜欢的字符串是长度为 $n$ 的字符串 $s$，名字必须包含 $s$ 作为子序列；
• 小红最喜欢的字符串是长度为 $m$ 的字符串 $t$，名字必须包含 $t$ 作为子序列；
• 名字中任意两个相同的字符之间必须间隔至少 $k$ 个其他字符。

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

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

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

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

输入格式

第一行输入三个整数 $n,m,k$。

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

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

输出格式

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

10 10 0
hottokeiki
hottokeiki

10

10 10 1
hottokeiki
hottokeiki

11

10 10 3
hottokeiki
hottokeiki

15

6 9 0
Jouhou
Orinpikku

14

9 7 1
Committee
teRRaCe

15

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$ 的限制。

数据范围

对于 $100\%$ 的数据满足：$1\leq n,m\leq 500$，$0\leq k\leq 3$。保证输入的字符串只包含字母字符。