#include<bits/stdc++.h>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=305;
char S[maxn];
int dp[2][maxn][maxn],n,m,o,ans;
int main() {
	scanf("%s",S+1);n=strlen(S+1);scanf("%d",&m);
	for(re int p=0;p<=m;++p,o^=1) {
		for(re int i=1;i<=n;i++) dp[o^1][i][i]=1;
		for(re int l=2;l<=n;++l) 
			for(re int i=1,j=i+l-1;j<=n;++i,++j) {
				dp[o^1][i][j]=max(dp[o^1][i][j-1],dp[o^1][i+1][j]);
				if(S[i]==S[j]) dp[o^1][i][j]=(dp[o^1][i][j],dp[o^1][i+1][j-1]+2);
				if(p) dp[o^1][i][j]=max(dp[o^1][i][j],dp[o][i+1][j-1]+2);
			}
		ans=max(ans,dp[o^1][1][n]);
	}
	printf("%d\n",ans);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 305;
int dp[MAXN][MAXN][MAXN];

int main()
{
    string s;
    cin >> s;
    int k;
    cin >> k;
    for(int sz = 1; sz <= s.size(); sz++){
        for(int l = 0; l < s.size() - sz + 1; l++){
            int r = l + sz - 1;
            for(int j = 0; j <= k; j++){
                if(r == l){
                    dp[l][r][j] = 1;
                    continue;
                }
                if(r - l == 1){
                    if(j == 0){
                        if(s[l] == s[r]){
                            dp[l][r][j] = 2;
                        }
                        else{
                            dp[l][r][j] = 1;
                        }
                    }
                    else{
                        dp[l][r][j] = 2;
                    }
                    continue;
                }
                dp[l][r][j] = max(dp[l + 1][r][j], dp[l][r - 1][j]);
                if(s[l] == s[r]){
                    dp[l][r][j] = max(dp[l][r][j], dp[l + 1][r - 1][j] + 2);
                }
                else if(j != 0){
                    dp[l][r][j] = max(dp[l][r][j], dp[l + 1][r - 1][j - 1] + 2);
                }
            }
        }
    }
    cout << dp[0][s.size() - 1][k];
}
