output_description: Print the highest possible value achievable.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
      K
attempt: # coding=utf-8
  
  
  def lcs(s1, s2):
      table = []
      for _ in range(100):
          table.append([0 for _ in range(100)])
  
      for y in range(1, len(s1) + 1):
          for x in range(1, len(s2) + 1):
              match = 0
              if s1[y - 1] == s2[x - 1]:
                  match = 1
  
              v1 = table[y - 1][x - 1] + match
              v2 = table[y - 1][x]
              v3 = table[y][x - 1]
              table[y][x] = max(v1, v2, v3)
      return table[len(s1)][len(s2)]
  
  
  def log(s, s2):
      return
      print("---")
      print("s :" + "".join(s))
      print("s2:" + "".join(s2))
  
  
  s = list(input())
  k = int(input())
  s2 = s[::-1]
  log(s, s2)
  
  ab = set(s)
  
  for i in range(k):
      idx = -1
      char = ""
      r = -1
      for j in range(len(s)):
          for x in ab:
              t = s[:]
              t[j] = x
              t2 = t[::-1]
              if lcs(t, t2) > r:
                  r = lcs(t, t2)
                  idx = j
                  char = x
  
      s[idx] = char
      s2 = s[::-1]
      log(s, s2)
  
  
  print(lcs(s, s2))
  
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"}]