#include <bits/stdc++.h>
#define sz(x) signed(size(x))
using namespace std;
using ll = long long;
using LL = long long;

inline void solve() {
    string s;
    int n;
    cin >> s >> n;
    
    vector<int> f(s.size());
    for (int i = 1, j = 0 ; i < s.size(); i++) {
        while (j && s[i] != s[j]) j = f[j - 1];
        if (s[i] == s[j]) f[i] = ++j;
    }

    vector<int> c(s.size(), 1);
    for (int i = 0; i < s.size(); i++) {
        if (f[i]) c[i] += c[f[i] - 1];
    }
    /*
    for (int i = 0; i < n; i++) cout << f[i] << ' ';
    cout << '\n';
    for (int i = 0; i < n; i++) cout << c[i] << ' ';
    cout << '\n';
    */  
    LL linf = 2e18;
    vector<LL> dp(s.size() + 1, -linf);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        vector<LL> nxt(s.size() + 1, -linf);
        nxt[0] = 0;
        for (int j = s.size(); j > 0; --j) {
            dp[f[j - 1]] = max(dp[f[j - 1]], dp[j]);
        }

        for (int j = s.size(); j >= 0; --j) {
            if (j < s.size()) nxt[j + 1] = max(nxt[j + 1], dp[j] + c[j]);
        }
                dp.swap(nxt);
    }

    LL mx = *max_element(dp.begin(), dp.end());
    cout << mx << '\n';
    
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--)
        solve();
    return 0;
}