/*
    題意：給出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;
}