/*
    题意：给出A,B串，问最小代价将B变为A的子串，代价不能超过LIM
           A<=10^6, B<=1000,LIM<=30

   经典编辑距离方程为
        dp[i,j] = min( dp[i-1,j-1]+(A[i]!=B[j]) , dp[i-1,j]+1 , dp[i,j-1]+1)
        dp[0,0]=0
   O(nm)
   现在允许B是A的子串，只需初始化时 dp[i,0] = 0 即可 但还是O(nm)

   由于要求代价<=LIM，所以打算对于会超过这个代价的dp[i,j]不去计算
   这样子平均复杂度为O(n*LIM)

   用一个last记录上一行最后需要计算的合法位置
   由于dp[i,j]相邻元素相差不超过1，最好的情况是dp[i,last+1] = LIM，这时dp[i-1,last] = LIM
   而dp[i,last+2],dp[i,last+3]等肯定会大于LIM！！
   所以对于当前行，我们只需计算到last+1即可！！

   由此得到算法：（有点像归纳）
   初始时last = LIM  因为dp[0,LIM] = LIM
   对于当前行，只需计算到last+1处即可
   若dp[now,last]>LIM  再调整一下

   启示：平常要计算整个n*m的表
          现在只计算每一行的前面一些元素，因为后面的那些代价会超过LIM！
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

inline int min(int a,int b){return a<b?a:b;}

const int MAXN = 1000010;

char A[MAXN],B[1010];
int dp[2][1010];

int main()
{
    //freopen("in","r",stdin);
    int lim;
    while(~scanf("%s%s",A+1,B+1))
    {
        scanf("%d",&lim);
        //dp[i,j] = min{ dp[i-1,j]+1 , dp[i,j-1]+1 , dp[i-1,j-1]+(A[i]!=B[j]) }
        //dp[i,0] = 0
        //ans = min{ dp[i,len] }
        for(int j=0;j<=lim;j++)dp[0][j] = j;
        int len = strlen(B+1);
        int ans = lim+1,last = min(lim,len);//last记录上一次最后计算的位置 当前最多计算的位置为last+1
        int pre = 0,now = 1;
        for(int i=1,j;A[i];i++)
        {
            dp[now][0] = 0;
            for(j=1;j<=last;j++)
            {
                dp[now][j] = min(dp[pre][j],dp[now][j-1])+1;
                dp[now][j] = min(dp[now][j],dp[pre][j-1]+(A[i]!=B[j]));
            }
            //j = last+1
            dp[now][j] = min(dp[now][j-1]+1,dp[pre][j-1]+(A[i]!=B[j]));
            if(j>=len)ans = min(ans,dp[now][len]);
            last = min(len,last+1);
            while(dp[now][last]>lim)last--;            
            swap(pre,now);            
        }
        printf("%d\n",ans>lim?-1:ans);
    }
    return 0;
}