#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long //instead of int main, use signed main
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef vector<int> vi;
typedef vector<vi> vvi;

signed main(){
    IOS;

    string s; cin >> s;
    int n; cin >> n;

    int slen = s.length();
    vi fail(slen);
    for(int i = 1, j = 0; i < s.length(); i++){
        while(j && s[i] != s[j]) j = fail[j - 1];
        if(s[i] == s[j]) fail[i] = ++j;
    }

    vi cnt(slen, 1);
    for(int i = 1; i < s.length(); i++){
        if(fail[i]) cnt[i] += cnt[fail[i] - 1];
    }

    vi dp(slen + 1, -1e18);
    dp[0] = 0;
    for(int i = 0; i < n; i++){
        vi nxt(slen + 1, -1e18); nxt[0] = 0;
        for(int j = slen; j >= 0; j--){
            if(j < slen) nxt[j + 1] = max(nxt[j + 1], dp[j] + cnt[j]);
            if(j) dp[fail[j - 1]] = max(dp[fail[j - 1]], dp[j]);
        }
        swap(dp, nxt);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}