/*
    題意：給出A,B串，問最小代價(jià)將B變?yōu)锳的子串，代價(jià)不能超過LIM
           A<=10^6, B<=1000,LIM<=30

   經(jīng)典編輯距離方程為
        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)
   現(xiàn)在允許B是A的子串，只需初始化時(shí) dp[i,0] = 0 即可 但還是O(nm)

   由于要求代價(jià)<=LIM，所以打算對(duì)于會(huì)超過這個(gè)代價(jià)的dp[i,j]不去計(jì)算
   這樣子平均復(fù)雜度為O(n*LIM)

   用一個(gè)last記錄上一行最后需要計(jì)算的合法位置
   由于dp[i,j]相鄰元素相差不超過1，最好的情況是dp[i,last+1] = LIM，這時(shí)dp[i-1,last] = LIM
   而dp[i,last+2],dp[i,last+3]等肯定會(huì)大于LIM?。?br>   所以對(duì)于當(dāng)前行，我們只需計(jì)算到last+1即可！！

   由此得到算法：（有點(diǎn)像歸納）
   初始時(shí)last = LIM  因?yàn)閐p[0,LIM] = LIM
   對(duì)于當(dāng)前行，只需計(jì)算到last+1處即可
   若dp[now,last]>LIM  再調(diào)整一下

   啟示：平常要計(jì)算整個(gè)n*m的表
          現(xiàn)在只計(jì)算每一行的前面一些元素，因?yàn)楹竺娴哪切┐鷥r(jià)會(huì)超過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記錄上一次最后計(jì)算的位置 當(dāng)前最多計(jì)算的位置為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;
}