#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
using namespace std;
using i64 = long long;
using i128 = __int128_t;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }

const int N = 2005;
int n, fail[N], cost[N], dp[N][N], m, lcp[N];
char s[N];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

    cin >> (s + 1) >> m;
    n = strlen(s + 1);

    rep(i, 1, n) {
        int j = 0;
        while (i + j <= n && s[i + j] == s[j + 1]) ++j;
        lcp[i] = j;
    }
    for (int i = 2, j = 0; i <= n; ++i) {
        while (j && s[j + 1] != s[i]) j = fail[j];
        if (s[j + 1] == s[i]) ++j;
        fail[i] = j;
    }
    rep(i, 1, n) {
        rep(len, fail[i] + 1, i) {
            int pos = i - len + 1;
            cost[i] += min(lcp[pos], len);
        }
    }

    memset(dp, 0xcf, sizeof dp);
    dp[1][0] = 0;
    rep(i, 1, m) {
        rep(j, 1, m - i + 1) up(dp[i][j], dp[i][j - 1]);
        rep(j, 1, m - i + 1) up(dp[i + j - fail[j]][fail[j]], dp[i][j] + cost[j]);
    }
    cout << dp[m + 1][0] << "\n";

	return 0;
}