#if not _GLIBCXX_DEBUG
#define NDEBUG 1
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define loop(i, l, r) for(int i=(int)(l); i<=(int)(r); i++)
#define rloop(i, l, r) for(int i=(int)(l); i>=(int)(r); i--)
#define all(x) (x).begin(), (x).end()

template<typename T>
ostream &operator<<(ostream &os, vector<T> a) {
  os << "[";
  for (auto it : a)
    os << it << ",";
  os << "]";
  return os;
}

template<typename T, typename T2>
ostream &operator<<(ostream &os, pair<T, T2> a) {
  os << "{";
  os << a.fi << sp << a.se;
  os << "}";
};

const int INF = numeric_limits<int>::max() / 2;

const int N = 2005;
#if _GLIBCXX_DEBUG
const int B1 = 100, B2 = 100, M1 = 1500450271, M2 = 1007050321;
#else
const int B1 = 71, B2 = 59, M1 = 1500450271, M2 = 1007050321;
#endif

int p1[N], p2[N];
void prepP() {
  p1[0] = 1;
  p2[0] = 1;
  for (int i = 1; i < N; i++) {
    p1[i] = 1LL * p1[i - 1] * B1 % M1;
    p2[i] = 1LL * p2[i - 1] * B2 % M2;
  }
}


class HashX {
public:
  int h1[N], h2[N];
  void prepHash(string s) {
    h1[0] = h2[0] = 0;
    for (int i = 1; i <= s.size(); i++) {
      h1[i] = (1LL * h1[i - 1] * B1 + s[i - 1]) % M1;
      h2[i] = (1LL * h2[i - 1] * B2 + s[i - 1]) % M2;
    }
  }
  pair<int, int> get(int L, int R) {
	  L++;
    int len = R - L + 1;
    int ans1 = (h1[R] - 1LL * h1[L - 1] * p1[len]) % M1;
    int ans2 = (h2[R] - 1LL * h2[L - 1] * p2[len]) % M2;
    ans1 += (ans1 < 0 ? M1 : 0);
    ans2 += (ans2 < 0 ? M2 : 0);
    return {ans1, ans2};
  }
} h;

string s;
int n;
int dp[N][N];

pair<int, int> state[N][26];

void prepState() {


	h.prepHash(s);
	std::map<int,int> prefixHashes;
	for(int i=1;i<=s.size();i++){
		prefixHashes[h.get(0,i).first]++;
	}


  loop(i, 0, s.size()) {
    //string str = s.substr(0, i);

    for (char c = 'a'; c <= 'z'; c++) {
      //str += c;

	  int nexti=i+1;
	  while(nexti!=0 and h.get(0,nexti).first!=[&]{
		  auto targethash=h.get(i+1-nexti,i);
		  targethash={
			  (int64_t(targethash.first)*B1+c) % M1,
			  (int64_t(targethash.second)*B2+c) % M2,
		  };
		  return targethash;
	  }().first) nexti--;


	  int cnt=0;
	  for(int j=0;j<=i;j++){
		  auto targethash=h.get(j,i);
		  if(j>i) assert(targethash.first==0);
		  targethash={
			  (int64_t(targethash.first)*B1+c) % M1,
			  (int64_t(targethash.second)*B2+c) % M2,
		  };
		  cnt+=prefixHashes[targethash.first];
	  }

	  //assert(i!=2);

	  state[i][c-'a']={nexti,cnt};
	  //assert(std::cerr<<i<<' '<<c<<' '<<nexti<<' '<<cnt<<'\n');

    }
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> s >> n;

  prepP();
  h.prepHash(s);
  //s = "!" + s;

  prepState();

  loop(i, 0, N - 1)
    loop(j, 0, N - 1)
      dp[i][j] = -INF;
  dp[0][0] = 0;
  loop(i, 0, n) {
    loop(j, 0, s.size()) {
      if (dp[i][j] == -INF)
        continue;
      for (char c = 'a'; c <= 'z'; c++) {
        auto trans = state[j][c - 'a'];
        dp[i + 1][trans.fi] = max(dp[i + 1][trans.fi], dp[i][j] + trans.se);
      }
    }
  }

  int ans = 0;
  loop(i, 0, s.size())
    ans = max(ans, dp[n][i]);

  cout << ans << endl;
}