output_description: Print the highest possible value achievable.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
      K
attempt: 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)))
  
problem_description: 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.
samples: [{"input": "abcabcabc\n    1", "output": "7\n    \n\nChanging the first character to `c` results in `cbcabcabc`. Let this tring be\nT, then one longest common subsequence of T and T' is `cbabcbc`, whose length\nis 7.\n\n* * *"}, {"input": "atcodergrandcontest\n    3", "output": "15"}]