P11202 [JOIG 2024] 名前 / Name

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】 字符串 `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$ 分）无附加条件。