#include <bits/stdc++.h>
using namespace std;
int Qread()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x;
}
int get_str(char *S)
{
    int len=1;
    do S[1]=getchar();while(S[1]<'a'||S[1]>'z');
    do S[++len]=getchar();while(S[len]>='a'&&S[len]<='z');
    S[len]=0;
    return len-1;
}
namespace SAM{
    struct Node{
        int nxt[26];
        int link,len;
        int minn,maxn;
    }s[100010];
    int poi_cnt;
    vector<int> son[100010];
    void reset(){poi_cnt=0,memset(s[0].nxt,0,sizeof(s[0].nxt)),s[0].link=-1,s[0].minn=s[0].maxn=0;}
    int get_node(){++poi_cnt;memset(s[poi_cnt].nxt,0,sizeof(s[poi_cnt].nxt)),s[poi_cnt].link=s[poi_cnt].len=s[poi_cnt].maxn=0,s[poi_cnt].minn=20070610;return poi_cnt;}
    int insert_node(int las,int nw,int ind)
    {
        int cur=get_node();
        s[cur].len=s[las].len+1;
        s[cur].maxn=s[cur].minn=ind;
        int p=las;
        while(p!=-1&&!s[p].nxt[nw])
        {
            s[p].nxt[nw]=cur;
            p=s[p].link;
        }
        if(p==-1) s[cur].link=0;
        else
        {
            int q=s[p].nxt[nw];
            if(s[p].len+1==s[q].len) s[cur].link=q;
            else
            {
                int clo=get_node();
                memcpy(s[clo].nxt,s[q].nxt,sizeof(s[q].nxt));
                s[clo].link=s[q].link;
                s[clo].len=s[p].len+1;
                while(p!=-1&&s[p].nxt[nw]==q)
                {
                    s[p].nxt[nw]=clo;
                    p=s[p].link;
                }
                s[q].link=s[cur].link=clo;
            }
        }
        return cur;
    }
    long long w[50010];
    long long k[50010];
    void add_cs(int l,int r,int b){if(l<=r) w[l]+=b,w[r+1]-=b;}
    void add_func(int l,int r,int a,int b){if(l<=r) k[l]+=a,k[r+1]-=a,w[l]+=b,w[r+1]-=b;}
    void dfs(int a)
    {
        for(int v:son[a])
        {
            dfs(v);
            s[a].maxn=max(s[a].maxn,s[v].maxn);
            s[a].minn=min(s[a].minn,s[v].minn);
        }
        if(a)
        {
            int len_=s[s[a].link].len+1;
            add_cs(s[a].minn,s[a].maxn-s[a].len,s[a].len-len_+1);
            add_func(max(s[a].minn,s[a].maxn-s[a].len+1),s[a].maxn-len_,-1,s[a].maxn-len_+1);
        }
    }
    long long solve(char *S,int len)
    {
        reset();
        w[0]=k[0]=0;
        for(int i=1,las=0;i<=len;i++) las=insert_node(las,S[i]-'a',i),w[i]=k[i]=0;
        for(int i=0;i<=poi_cnt;i++) son[i].clear();
        for(int i=1;i<=poi_cnt;i++) son[s[i].link].push_back(i);
        dfs(0);
        for(int i=1;i<=len;i++) w[i]+=w[i-1],k[i]+=k[i-1];
        long long ret=0;
        for(int i=1;i<len;i++) ret+=(w[i]+k[i]*i)*(w[i]+k[i]*i);
        return ret;
    }
}
int n,k;
char S[50010];
map<pair<int,int>,long long> G;
long long get_slv(int l,int r)
{
    if(G[make_pair(l,r)]) return G[make_pair(l,r)];
    else return G[make_pair(l,r)]=SAM::solve(S+l-1,r-l+1);
}
int f[50010];
int tim[50010],stk[50010],rea,top;
bool chk(long long T)
{
    int cnt=0,l,r,mid,tk,fl=1;
    while(fl<=n)
    {
        tk=fl;
        for(l=0;l<20;l++) if(tk+(1<<l)<=n&&get_slv(fl,tk+(1<<l))<=T) tk+=(1<<l);else break;l--;
        for(;~l;l--) if(tk+(1<<l)<=n&&get_slv(fl,tk+(1<<l))<=T) tk+=(1<<l);
        fl=tk+1;
        cnt++;
    }
    return cnt<=k;
}
int main()
{
    n=get_str(S);
    get_slv(2,8);
    k=Qread();
    long long l=1,r=1e18,mid=0,ans=0;
    while(l<=r)
    {
        mid=(l+r>>1);
        if(chk(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}