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

B

小fa 在批改作业的时候发现大家的提交的文件名都很不规范，这让他很头疼。作为一个强迫症患者，他决定手动规范大家的文件名。但是有些人的文件名特别长，他想要知道最少需要修改多少次才能够使得字符串 $A$ 变成字符串 $B$。当然对于修改代价超过 $K$ 的文件名我们会选择放弃。

定义一次修改代价：

1. 在第 $i$ 个位置插入一个字符 $...S_{i-1}S_{i}S_{i+1}...\Rightarrow S_{i-1}KS_{i}S_{i+1}$

2. 删除第 $i$ 个位置的字符 $...S_{i-1}S_{i}S_{i+1}...\Rightarrow S_{i-1}S_{i+1}...$

输入格式

输入共包含 $3$ 行。

第 $1$ 行包含三个整数 $n,m,K$，分别表示原始串 $A$ 的长度,目标串 $B$ 的长度和限制的最大修改次数。

接下来 $2$ 行，分别输入原始字符串 $A$ 和目标字符串 $B$。

输出格式

输出共包含 $1$ 行，如果最小修改次数小于等于 $K$，则输出最少修改次数，不然输出 $-1$。

样例输入

3 4 2
bee
beef

1

数据范围

对于其中 $25\%$ 的数据，$n,m\le10$。

对于其中 $50\%$ 的数据，$n,m\le1000$。

对于另外 $25\%$ 的数据，$K\le10$。

对于全部数据：$0\le n,m\le500000\ \ \ 0\le K\le100$。字符串中只包含小写字母。