#include <bits/stdc++.h>
#if defined(__GNUC__)
#pragma GCC optimize ("Ofast")
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 310, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
int dp[MAXN][MAXN][MAXN];
string S;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>S>>k;
	n=S.size();
	S="."+S;
	for (int i=n; i; i--){
		for (int x=0; x<=k; x++) dp[i][i][x]=1;
		for (int j=i+1; j<=n; j++){
			dp[i][j][0]=max(dp[i+1][j][0], dp[i][j-1][0]);
			if (S[i]==S[j]) dp[i][j][0]=max(dp[i][j][0], dp[i+1][j-1][0]+2);
			for (int x=1; x<=k; x++){
				dp[i][j][x]=max(dp[i+1][j][x], dp[i][j-1][x]);
				dp[i][j][x]=max(dp[i][j][x], 2+dp[i+1][j-1][x-(S[i]!=S[j])]);
			}
		}
	}
	cout<<dp[1][n][k]<<'\n';
	
	return 0;
}

#include <algorithm>
#include <cctype>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 3e2+5;
int n, m, f[N][N][N], ans; char s[N];
int main()
{
    scanf("%s", s+1), n = strlen(s+1), m = read();
    for(int i = 1; i <= n; ++i) f[0][i][i] = 1;
    for(int k = 0; k <= m; ++k)
        for(int l = 2; l <= n; ++l)
            for(int i = 1, j = l; j <= n; ++i, ++j)
            {
                f[k][i][j] = max(f[k][i+1][j], f[k][i][j-1]);
                if(s[i] == s[j]) f[k][i][j] = max(f[k][i][j], f[k][i+1][j-1]+2);
                if(k) f[k][i][j] = max(f[k][i][j], f[k-1][i+1][j-1]+2);
            }
    for(int i = 0; i <= m; ++i) ans = max(ans, f[i][1][n]);
    printf("%d\n", ans);
    return 0;
}