Problem:


Score : 900 points

Problem Statement

Takahashi has decided to give a string to his mother.

The value of a string T is the length of the longest common subsequence of T and T', where T' is the string obtained by reversing T.
That is, the value is the longest length of the following two strings that are equal: a subsequence of T (possibly non-contiguous), and a subsequence of T' (possibly non-contiguous).

Takahashi has a string S. He wants to give her mother a string of the highest possible value, so he would like to change at most K characters in S to any other characters in order to obtain a string of the highest possible value.
Find the highest possible value achievable.

Constraints

1 \leq |S| \leq 300

0 \leq K \leq |S|

S consists of lowercase English letters.

K is an integer.

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the highest possible value achievable.

Sample Input 1

abcabcabc
1

Sample Output 1

7

Changing the first character to c results in cbcabcabc.
Let this tring be T, then one longest common subsequence of T and T' is cbabcbc, whose length is 7.

Sample Input 2

atcodergrandcontest
3

Sample Output 2

15



Sample input:
abcabcabc
1


Sample output:
7

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]

ans = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  ans= max(dp[sfl][sll][K]*2+1,dp[sfl][sll-1][K]*2+1+flg,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]

ans = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,K+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  ans= max(dp[sfl][sll][min(K,sll)]*2+1,dp[sfl][sll-1][min(K,sll)]*2+1+flg,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
if 2*K+1 >= n:
  print(n)
  exit()
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]

ans = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  ans= max(dp[sfl][sll][min(K,sll)]*2+1,dp[sfl][sll-1][min(K,sll)]*2+1+flg,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]
ans = min(2*K+1,n)
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  ans= max(dp[sfl][sll][min(K,sll)]*2+1,dp[sfl][sll-1][min(K,sll)]*2+1+flg,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
K = int(input())
n = len(s)
t = s[::-1]
dp = [[[0 for i in range(K+1)] for j in range(n+1)] for k in range(n+1)]
ansls = [min(2*K+1,n)]
for center in range(1,n-1):
  flg = 0
  sf = s[:center]
  sl = t[:n-center-1]
  if s[center] == s[center+1]:
    flg = 1
  sfl = len(sf)
  sll = len(sl)
  for j in range(1,sll+1):
    dp[sfl][j][0] = max(dp[sfl-1][j][0],dp[sfl][j-1][0])
    if sf[-1] != sl[j-1]:
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
    if sf[-1] == sl[j-1]:
      dp[sfl][j][0] = max(dp[sfl][j][0],dp[sfl-1][j-1][0]+1)
      for k in range(1,min(K,sll)+1):
        dp[sfl][j][k] = max(dp[sfl-1][j-1][k-1]+1,dp[sfl-1][j-1][k]+1,dp[sfl-1][j][k],dp[sfl][j-1][k])
  ansls.append(max(dp[sfl][sll][min(K,sll)]*2+1,dp[sfl][sll-1][min(K,sll)]*2+1+flg))
print(max(ansls))

Submission status: Wrong Answer

Solution code:
s = list(map(ord, list(input())))
ls = len(s)
lk = int(input())
if lk*2 >= ls: print(ls); exit(0)
lk *= 2
dp = [[[0]*(lk+1) for _ in range(ls+1)] for i in range(ls+1)]
for k in range(lk+1):
  for i in range(ls):
    for j in range(ls):
      if s[i] == s[-j-1]:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i][j][k] + 1)
      else:
        dp[i+1][j+1][k] = max(dp[i+1][j+1][k], dp[i+1][j][k], dp[i][j+1][k], (k > 0)*(dp[i][j][k-1] + 1))
print(max(dp[ls][ls]))

Submission status: Wrong Answer

Solution code:
def lcs(str1, str2):
    '''文字列str1, str2の最長共通部分列(Lowest Common Subsequence, LCS)を求める
    計算量O(len(str1)*len(str2))  
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

    return dp[len(str1)][len(str2)]


s = input()
n = len(s)
k = int(input())

ans = 0
for i in range(n):
    t = s[0:i]
    rev_t = s[i+1:][::-1]
    min_len = min(len(t), len(rev_t))
    ans = max(min(lcs(t, rev_t) + k, min_len) * 2 + 1, ans)

for i in range(n + 1):
    t = s[0:i]
    rev_t = s[i:][::-1]
    min_len = min(len(t), len(rev_t))
    ans = max(min(lcs(t, rev_t) + k, min_len) * 2, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


def LCS_words(X,Y):
    X,Y=" "+X," "+Y
    m,n=len(X),len(Y)
    MAP=[[0 for i in range(m)] for j in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if Y[i]==X[j]:
                MAP[i][j]=MAP[i-1][j-1]+1
            else:
                MAP[i][j]=max(MAP[i][j-1],MAP[i-1][j])
    #print(np.array(MAP))
    return MAP[n-1][m-1]


s=input()
k=int(input())
base=LCS_words(s,s[::-1])
reverse=s[::-1]

for i in range(len(s)//2):
    if k==0:break
    if [s[i],reverse[-i]]==[reverse[i],reverse[-i]]:
        base +=2
        k -=1

print(base+k)

Submission status: Wrong Answer

Solution code:
def LCS_words(X,Y):
    X,Y=" "+X," "+Y
    m,n=len(X),len(Y)
    MAP=[[0 for i in range(m)] for j in range(n)]
    for i in range(1,n):
        for j in range(1,m):
            if Y[i]==X[j]:
                MAP[i][j]=MAP[i-1][j-1]+1
            else:
                MAP[i][j]=max(MAP[i][j-1],MAP[i-1][j])
    return MAP[n-1][m-1]


s=input()
k=int(input())
print(LCS_words(s,s[::-1])+k*2)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

S = list(map(ord, readline().strip()))
N = len(S)
S = [None] + S + [None]
K = int(readline())
dp = [[[0]*(K+1) for _ in range(N+2)] for _ in range(N+2)]
for i in range(1, N+1):
    dp[i][i][0] = 1
for i in range(1, N):
    if S[i] == S[i+1]:
        dp[i][i+1][0] = 2
    elif K:
        dp[i][i+1][0] = 1
        dp[i][i+1][1] = 2
for s in range(3, N+1):
    for i in range(1, N-s+2):
        j = i+s-1
        if S[i] == S[j]:
            for k in range(K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], 2+dp[i+1][j-1][k])
        else:
            dp[i][j][0] = max(dp[i+1][j][0], dp[i][j-1][0], dp[i+1][j-1][0])
            for k in range(1, K+1):
                dp[i][j][k] = max(dp[i+1][j][k], dp[i][j-1][k], dp[i+1][j-1][k], 2+dp[i+1][j-1][k-1], dp[i+1][j-1][k])
print(max(dp[1][N][k] for k in range(K+1)))

Submission status: Wrong Answer

Solution code:
def solve(s, k):
    n = len(s)
    if k >= n // 2:
        return n
    pdp = [[0] * (k + 1)]
    for l in range(1, n + 1):
        i = n - l
        dp = [[0] * (k + 1) for _ in range(l + 1)]
        dpr1, pdpr1 = dp[-1], [0] * (k + 1)
        for r in range(l):
            dpr, pdpr = dp[r], pdp[r - 1]
            inc = 2 if r else 1
            if s[i] == s[i + r]:
                for p in range(k + 1):
                    dp[r] = [c + inc for c in pdpr1]
            else:
                dpr[0] = max(pdpr[0], dpr1[0])
                for p in range(1, k + 1):
                    dpr[p] = max(pdpr[p], dpr1[p], pdpr1[p - 1] + inc)
            dpr1, pdpr1 = dpr, pdpr
        pdp = dp

    return pdp[-2][k]


print(solve(input(), int(input())))

Submission status: Wrong Answer

Solution code:
def solve(s, k):
    n = len(s)
    dp = [[[0] * (k + 1) for _ in range(n)] for _ in range(n + 1)]
    for l in range(n - 1, -1, -1):
        dpl, dpl1 = dp[l], dp[l + 1]
        for r in range(l, n):
            dpr, dpr1 = dpl[r], dpl1[r - 1]
            inc = 1 if l == r else 2
            for p in range(k + 1):
                if s[l] == s[r]:
                    dpr[p] = dpr1[p] + inc
                else:
                    dpr[p] = max(dpl1[r][p], dp[l][r - 1][p])
                    if p:
                        dpr[p] = max(dpr[p], dpr1[p - 1] + inc)
    return dp[0][-1][k]


print(solve(input(), int(input())))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
S=raw_input()
L=len(S)
K=input()

dp = defaultdict(lambda: 0)

for i in range(L):
	for j in range(K+1):
		dp[(i,i,j)]=1

for i in range(1,L):			#i:width
	for j in range(1,L-i+1):	#j:start point
		l=j
		r=j+i
		for k in range(K+1):
			dp[(l,r,k)] = max(dp[(l+1,r,k)], dp[(l,r-1,k)]);
			if(S[l-1] == S[r-1]):
				dp[(l,r,k)] = max(dp[(l,r,k)], dp[(l+1,r-1,k)] + 2);
			else:
				if(k):
					dp[(l,r,k)] = max(dp[(l,r,k)], dp[(l+1,r-1,k-1)] + 2);

print dp[(1,L,K)]

Submission status: Wrong Answer

Solution code:
S=input()
K=int(input())
S2=S[::-1]
l=len(S)

dp=[[0 for x in range(l+1)] for y in range(l+1)]
trace=[[0 for x in range(l+1)] for y in range(l+1)]
for i in range(l+1):
  trace[i][0]=-1
  trace[0][i]=-1

for i in range(l):
  for j in range(l):
    if S[i]==S2[j]:
      dp[i+1][j+1]=dp[i][j]+1
      trace[i+1][j+1]=1
    elif dp[i+1][j] > dp[i][j+1]:
      dp[i+1][j+1]=dp[i+1][j]
      trace[i+1][j+1]=2
    else:
      dp[i+1][j+1]=dp[i][j+1]
      trace[i+1][j+1]=3
cnt=[0 for t in range(l+1)]
def tracedo(trace,a,b):
  if trace[a][b]==-1:
    return
  elif trace[a][b]==2:
    tracedo(trace,a,b-1)
  elif trace[a][b]==3:
    tracedo(trace,a-1,b)
  else:
    tracedo(trace,a-1,b-1)
    cnt[a-1]=1
  return

tracedo(trace,l,l)
ans=0
for i in range(l):
  if cnt[i]==0 and cnt[l-i-1]==0 and i!=(l-i-1):
    ans+=2
  elif cnt[i]==0 and cnt[l-i-1]==0 and i==(l-i-1):
    ans+=1
print(dp[l][l]+min(ans,K*2))

Submission status: Wrong Answer

Solution code:
S=input()
K=int(input())
S2=S[::-1]
l=len(S)

dp=[[0 for x in range(l+1)] for y in range(l+1)]
trace=[[0 for x in range(l+1)] for y in range(l+1)]
for i in range(l+1):
  trace[i][0]=-1
  trace[0][i]=-1

for i in range(l):
  for j in range(l):
    if S[i]==S2[j]:
      dp[i+1][j+1]=dp[i][j]+1
      trace[i+1][j+1]=1
    elif dp[i+1][j] > dp[i][j+1]:
      dp[i+1][j+1]=dp[i+1][j]
      trace[i+1][j+1]=2
    else:
      dp[i+1][j+1]=dp[i][j+1]
      trace[i+1][j+1]=3
cnt=[0 for t in range(l+1)]
def tracedo(trace,a,b):
  if trace[a][b]==-1:
    return
  elif trace[a][b]==2:
    tracedo(trace,a,b-1)
  elif trace[a][b]==3:
    tracedo(trace,a-1,b)
  else:
    tracedo(trace,a-1,b-1)
    cnt[a-1]=1
  return

tracedo(trace,l,l)
ans=0
for i in range(l):
  if cnt[i]==0 and cnt[l-i-1]==0:
    ans+=1
print(dp[l][l]+min(ans*2,K*2))

Submission status: Wrong Answer

Solution code:
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

S = raw_input()
K = int(raw_input())

revstr = S[::-1]

charset = set(S)

def replace_calclcs(i, candstrlist):
    newcand = candstrlist[:]
    for candstr, maxlcs in candstrlist:
        for char in charset:
            newrevstr = candstr[:i] + char + candstr[i+1:]
            newlcs = lcs(S, newrevstr)
            if(newlcs > maxlcs):
                newcand.append([newrevstr, newlcs])
    return newcand

cands = [[revstr, lcs(S, revstr)]]
for i in range(len(revstr)):
    cands = replace_calclcs(i, cands)

print(max(map(lambda x: x[1], cands)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
K = int(input())
n = len(s)
dp = [[[0]*(K+1) for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(K+1):
        dp[i][i+1][j] = 1
for l in range(2, n+1):
    for i in range(n-l+1):
        for k in range(K+1):
#             print(l, i, i+l, j)
            if s[i]==s[i+l-1]:
                dp[i][i+l][k] = dp[i+1][i+l-1][k] + 2
            else:
                dp[i][i+l][k] = max(dp[i+1][i+l][k], dp[i][i+l-1][k])
                if k>=1:
                    dp[i][i+l][k] = max(dp[i][i+l][k], dp[i+1][i+l-1][k-1]+2)
ans = max(dp[0][n][j] for j in range(K+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

# 参考 https://atcoder.jp/contests/agc021/submissions/8392122
def examB():
    def norm2(vec):
        return math.sqrt(vec[0] ** 2 + vec[1] ** 2)
    # any 2 points must have different position.
    def ConvexHull(point_list):
        pos2idx = {point_list[i]: i for i in range(len(point_list))}
        y_val = defaultdict(list)
        x_list = sorted(list(set([p[0] for p in point_list])))
        for x, y in point_list:
            y_val[x].append(y)

        upper = [(x_list[0], max(y_val[x_list[0]]))]
        lower = [(x_list[0], min(y_val[x_list[0]]))]
        prev = float('inf')
        for xi in x_list[1:]:
            x0, y0 = upper[-1]
            x1, y1 = xi, max(y_val[xi])
            if (y1 - y0) / (x1 - x0) < prev:
                upper.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = upper[-1]
                    if len(upper) == 1:
                        upper.append((x1, y1))
                        break
                    x00, y00 = upper[-2]
                    if (y1 - y0) / (x1 - x0) > (y1 - y00) / (x1 - x00):
                        upper.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        upper.append((x1, y1))
                        break

        prev = -float('inf')
        for xi in x_list[1:]:
            x0, y0 = lower[-1]
            x1, y1 = xi, min(y_val[xi])
            if (y1 - y0) / (x1 - x0) > prev:
                lower.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = lower[-1]
                    if len(lower) == 1:
                        lower.append((x1, y1))
                        break
                    x00, y00 = lower[-2]
                    if (y1 - y0) / (x1 - x0) < (y1 - y00) / (x1 - x00):
                        lower.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        lower.append((x1, y1))
                        break

        # return upper, lower
        # return [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]

        upper_idx, lower_idx = [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]
        if upper_idx[-1] == lower_idx[-1]:
            upper_idx.pop()
        CH_idx = upper_idx
        CH_idx.extend(reversed(lower_idx))
        if CH_idx[0] == CH_idx[-1] and len(CH_idx) > 1:
            CH_idx.pop()
        return CH_idx

    N = I()
    P = [[]for _ in range(N)]
    D = defaultdict(int)
    for i in range(N):
        x,y = LI()
        P[i] = (x,y)
        D[(x,y)] = i
    C = ConvexHull(P)
    ans = [0]*N
    if len(C)==2:
        for c in C:
            ans[c] = 0.5
        for v in ans:
            print(v)
        return
    #print(C)
    for i,c in enumerate(C):
        s, t, u = C[i - 1], C[i], C[(i + 1) % len(C)]
        x0, y0 = P[s]
        x1, y1 = P[t]
        x2, y2 = P[u]
        vec0 = (y0 - y1, x1 - x0)
        vec1 = (y1 - y2, x2 - x1)
        ans[t] =  math.acos((vec0[0] * vec1[0] + vec0[1] * vec1[1]) / (norm2(vec0) * norm2(vec1))) / (2 * math.pi)
    for v in ans:
        print(v)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    K = I()
    dp = defaultdict(lambda:[0 for _ in range(K+1)])
    for i in range(N):
        for j in range(K+1):
            dp[(i,i)][j] = 1
    for i in range(2,N+1):
        for k in range(K+1):
            for l,r in enumerate(range(i-1,N)):
                if S[l]==S[r]:
                    dp[(l,r)][k] = dp[(l+1,r-1)][k] + 2
                else:
                    if k>0:
                        dp[(l,r)][k] = max(dp[(l+1,r)][k],dp[(l,r-1)][k],dp[(l+1,r-1)][k-1]+2)
                    else:
                        dp[(l,r)][k] = max(dp[(l + 1,r)][k], dp[(l,r - 1)][k])
    ans = max(dp[(0,N-1)])
    #print(dp)
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

# 参考 https://atcoder.jp/contests/agc021/submissions/8392122
def examB():
    def norm2(vec):
        return math.sqrt(vec[0] ** 2 + vec[1] ** 2)
    # any 2 points must have different position.
    def ConvexHull(point_list):
        pos2idx = {point_list[i]: i for i in range(len(point_list))}
        y_val = defaultdict(list)
        x_list = sorted(list(set([p[0] for p in point_list])))
        for x, y in point_list:
            y_val[x].append(y)

        upper = [(x_list[0], max(y_val[x_list[0]]))]
        lower = [(x_list[0], min(y_val[x_list[0]]))]
        prev = float('inf')
        for xi in x_list[1:]:
            x0, y0 = upper[-1]
            x1, y1 = xi, max(y_val[xi])
            if (y1 - y0) / (x1 - x0) < prev:
                upper.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = upper[-1]
                    if len(upper) == 1:
                        upper.append((x1, y1))
                        break
                    x00, y00 = upper[-2]
                    if (y1 - y0) / (x1 - x0) > (y1 - y00) / (x1 - x00):
                        upper.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        upper.append((x1, y1))
                        break

        prev = -float('inf')
        for xi in x_list[1:]:
            x0, y0 = lower[-1]
            x1, y1 = xi, min(y_val[xi])
            if (y1 - y0) / (x1 - x0) > prev:
                lower.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = lower[-1]
                    if len(lower) == 1:
                        lower.append((x1, y1))
                        break
                    x00, y00 = lower[-2]
                    if (y1 - y0) / (x1 - x0) < (y1 - y00) / (x1 - x00):
                        lower.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        lower.append((x1, y1))
                        break

        # return upper, lower
        # return [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]

        upper_idx, lower_idx = [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]
        if upper_idx[-1] == lower_idx[-1]:
            upper_idx.pop()
        CH_idx = upper_idx
        CH_idx.extend(reversed(lower_idx))
        if CH_idx[0] == CH_idx[-1] and len(CH_idx) > 1:
            CH_idx.pop()
        return CH_idx

    N = I()
    P = [[]for _ in range(N)]
    D = defaultdict(int)
    for i in range(N):
        x,y = LI()
        P[i] = (x,y)
        D[(x,y)] = i
    C = ConvexHull(P)
    ans = [0]*N
    if len(C)==2:
        for c in C:
            ans[c] = 0.5
        for v in ans:
            print(v)
        return
    #print(C)
    for i,c in enumerate(C):
        s, t, u = C[i - 1], C[i], C[(i + 1) % len(C)]
        x0, y0 = P[s]
        x1, y1 = P[t]
        x2, y2 = P[u]
        vec0 = (y0 - y1, x1 - x0)
        vec1 = (y1 - y2, x2 - x1)
        ans[t] =  math.acos((vec0[0] * vec1[0] + vec0[1] * vec1[1]) / (norm2(vec0) * norm2(vec1))) / (2 * math.pi)
    for v in ans:
        print(v)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    K = I()
    dp = [[[0 for _ in range(K+1)]for _ in range(N)]for _ in range(N)]
    for i in range(N):
        for j in range(K+1):
            dp[i][i][j] = 1
    for i in range(2,N+1):
        for k in range(K+1):
            for l,r in enumerate(range(i-1,N)):
                if S[l]==S[r]:
                    dp[l][r][k] = dp[l+1][r-1][k] + 2
                else:
                    if k>0:
                        dp[l][r][k] = max(dp[l+1][r][k],dp[l][r-1][k],dp[l+1][r-1][k-1]+2)
                    else:
                        dp[l][r][k] = max(dp[l + 1][r][k], dp[l][r - 1][k])
    ans = max(dp[0][-1])
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

# 参考 https://atcoder.jp/contests/agc021/submissions/8392122
def examB():
    def norm2(vec):
        return math.sqrt(vec[0] ** 2 + vec[1] ** 2)
    # any 2 points must have different position.
    def ConvexHull(point_list):
        pos2idx = {point_list[i]: i for i in range(len(point_list))}
        y_val = defaultdict(list)
        x_list = sorted(list(set([p[0] for p in point_list])))
        for x, y in point_list:
            y_val[x].append(y)

        upper = [(x_list[0], max(y_val[x_list[0]]))]
        lower = [(x_list[0], min(y_val[x_list[0]]))]
        prev = float('inf')
        for xi in x_list[1:]:
            x0, y0 = upper[-1]
            x1, y1 = xi, max(y_val[xi])
            if (y1 - y0) / (x1 - x0) < prev:
                upper.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = upper[-1]
                    if len(upper) == 1:
                        upper.append((x1, y1))
                        break
                    x00, y00 = upper[-2]
                    if (y1 - y0) / (x1 - x0) > (y1 - y00) / (x1 - x00):
                        upper.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        upper.append((x1, y1))
                        break

        prev = -float('inf')
        for xi in x_list[1:]:
            x0, y0 = lower[-1]
            x1, y1 = xi, min(y_val[xi])
            if (y1 - y0) / (x1 - x0) > prev:
                lower.append((x1, y1))
                prev = (y1 - y0) / (x1 - x0)
            else:
                while True:
                    x0, y0 = lower[-1]
                    if len(lower) == 1:
                        lower.append((x1, y1))
                        break
                    x00, y00 = lower[-2]
                    if (y1 - y0) / (x1 - x0) < (y1 - y00) / (x1 - x00):
                        lower.pop()
                    else:
                        prev = (y1 - y0) / (x1 - x0)
                        lower.append((x1, y1))
                        break

        # return upper, lower
        # return [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]

        upper_idx, lower_idx = [pos2idx[xy] for xy in upper], [pos2idx[xy] for xy in lower]
        if upper_idx[-1] == lower_idx[-1]:
            upper_idx.pop()
        CH_idx = upper_idx
        CH_idx.extend(reversed(lower_idx))
        if CH_idx[0] == CH_idx[-1] and len(CH_idx) > 1:
            CH_idx.pop()
        return CH_idx

    N = I()
    P = [[]for _ in range(N)]
    D = defaultdict(int)
    for i in range(N):
        x,y = LI()
        P[i] = (x,y)
        D[(x,y)] = i
    C = ConvexHull(P)
    ans = [0]*N
    if len(C)==2:
        for c in C:
            ans[c] = 0.5
        for v in ans:
            print(v)
        return
    #print(C)
    for i,c in enumerate(C):
        s, t, u = C[i - 1], C[i], C[(i + 1) % len(C)]
        x0, y0 = P[s]
        x1, y1 = P[t]
        x2, y2 = P[u]
        vec0 = (y0 - y1, x1 - x0)
        vec1 = (y1 - y2, x2 - x1)
        ans[t] =  math.acos((vec0[0] * vec1[0] + vec0[1] * vec1[1]) / (norm2(vec0) * norm2(vec1))) / (2 * math.pi)
    for v in ans:
        print(v)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    K = I()
    dp = [[[0 for _ in range(K+1)]for _ in range(N)]for _ in range(N)]
    for i in range(N):
        for j in range(K+1):
            dp[i][i][j] = 1
    for i in range(2,N+1):
        for k in range(K+1):
            for l,r in enumerate(range(i-1,N)):
                if S[l]==S[r]:
                    dp[l][r][k] = dp[l+1][r-1][k] + 2
                else:
                    if k>0:
                        dp[l][r][k] = max(dp[l+1][r][k],dp[l][r-1][k],dp[l+1][r-1][k-1]+2)
                    else:
                        dp[l][r][k] = max(dp[l + 1][r][k], dp[l][r - 1][k])
    ans = max(dp[0][-1])
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
k = int(input())

dp = [[[0] * (n + 1) for i in range(n + 1)] for i in range(k + 1)]

# 長さ1のときの初期化
for i in range(n):
    dp[0][i][i + 1] = 1

# 長さ2~nのときのDP
for length in range(2, n + 1):
    for l in range(n + 1):
        for ki in range(k + 1):
            r = l + length
            if r > n:
                break
            if s[l] == s[r - 1]:
                dp[ki][l][r] = max(2 + dp[ki][l + 1][r - 1], dp[ki][l][r])
            else:
                dp[ki][l][r] = max(dp[ki][l + 1][r], dp[ki][l][r - 1], dp[ki][l][r])
                if ki - 1 >= 0:
                    dp[ki][l][r] = max(dp[ki - 1][l + 1][r - 1] + 2, dp[ki - 1][l + 1][r - 1] + 2, dp[ki][l][r])

ans = 0
for i in range(k + 1):
    ans = max(ans, dp[i][0][-1])
print(ans)