题目描述

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

存在这么两种修改操作：

\(1\). 在第 \(i\) 个位置插入一个字符 \(c\)：\(S_{i-1},S_i,S_{i+1}\) ⇒ \(S_{i-1}, c, S_i,S_{i+1}\)；

\(2\). 删除第 \(i\) 个位置的字符：\(S_{i-1},S_i,S_{i+1}\) ⇒ \(S_{i-1},S_{i+1}\)。

格式

输入格式

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

接下来 \(2\) 行，分别包含原始字符串 \(A\) 和目标字符串 \(B\)。

输出格式

输出一行，如果最小修改次数小于等于 \(K\)，则输出最少修改次数，不然输出 \(-1\)。

样例1

样例输入1

3 4 2
bee
beef

样例输出1

1

限制

对于全部数据：\(0 ≤ n,m ≤ 500000,0 ≤ K ≤100\)。字符串中只包含小写字母。