Problem: 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.

Examples

Input

abcabcabc
1


Output

7


Input

atcodergrandcontest
3


Output

15

Solution (in PYTHON3):

Solution:

"""

https://atcoder.jp/contests/agc021/tasks/agc021_d

ある部分でcutしたとする。
前半と後半のLCSを求めたとすると、交差した後のLCSの長さも同じ
→左からindex iまでと右からindex jまでのLCSを求めればいい (i < j)
あとは、普通のLCSと同様のdpでいける

dp[i][j][k] = 左からi番目の文字までと、右からindex jの文字までのk回替えた際のLCS長さ
あとは2倍すれば大体行ける？
i+1 == jでは、2倍すればおk
i+1 < j では、真ん中の文字を使えるので、2倍して1足す

"""

import sys
S = input()
S = " "+S
K = int(input())
N = len(S)-1
if N == 1:
    print (1)
    sys.exit()
elif N == 2:
    if S[1] == S[2] or K > 0:
        print (2)
    else:
        print (1)
    sys.exit()

dp = [[[0] * (K+1) for i in range(N+2)]]
ans = 0

for i in range(1,N+1):

    dp.append( [[0] * (K+1) for i in range(N+2)] )

    for j in range(N,i,-1):

        for k in range(K+1):

            #同じ場合、どっちも進める
            if S[i] == S[j]:
                dp[i][j][k] = max( dp[i][j][k] , dp[i-1][j+1][k] + 1)
            else:
                dp[i][j][k] = max( dp[i][j][k] , dp[i-1][j][k] , dp[i][j+1][k] )
                if k != 0:
                    dp[i][j][k] = max(dp[i][j][k] , dp[i-1][j+1][k-1] + 1)

            if i+1 == j:
                ans = max(ans , dp[i][j][k] * 2)
            else:
                ans = max(ans , dp[i][j][k] * 2 + 1)

    dp[i-1] = []

print (ans)