#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb emplace_back
#define mkp make_pair
inline ll read(){ ll x; scanf("%lld",&x); return x; }
const ll mod = 998244353;
ll n,m,f[4005],jp[4005][26]; char s[4005];
ll dp[4005][4005],con[4005];
void solve(){
	scanf("%s",s+1); n=strlen(s+1);
	m=read(); con[1]=1;
//	memset(jp[1], -1, sizeof(jp[1]));
	for(ll i=0;i<=n;i++){
		if(i>1){
			f[i]=f[i-1];
			while(f[i] && s[f[i]+1] != s[i]) f[i]=f[f[i]];
			if(s[f[i]+1] == s[i]) f[i]++;
//			cout<<i<<" border "<<f[i]<<endl;
//			con[i]=con[f[i]]+1;
//			cout<<"at "<<con[i]<<endl;
		}
		for(ll j=0;j<26;j++){
			ll now=i;
			while(now && s[now+1] != j+'a') now=f[now];
			if(s[now+1] != j+'a') jp[i][j] = 0;
			else jp[i][j] = now+1;
//			cout<<i<<","<<(char)(j+'a')<<" : "<<jp[i][j]<<endl;
		}
	}
	memset(dp, 0xb0, sizeof(dp)); dp[0][0]=0;
	for(ll i=0;i<m;i++){
		for(ll j=0;j<=n;j++){
			for(ll k=0;k<26;k++){
				dp[i+1][jp[j][k]] = max(dp[i+1][jp[j][k]], dp[i][j]+con[jp[j][k]]);
			}
		}
	}
	ll ans=-1e18;
	for(ll i=0;i<=n;i++){
		ans=max(ans, dp[m][i]);
	}
	printf("%lld\n", ans);
}

int main(){
	ll T=1; while(T--) solve();
}