fun main(args: Array<String>) {
  val s = readLine()!!
  val k = readLine()!!.toInt()
  val n = s.length
  val dp = Array(n, { Array(n, { IntArray(k + 1, { -1 } ) })})

  // Max length of Palindrome sub-sequence
  // [l, r]: Range (closed)
  // c: Change
  fun doDP(l: Int, r: Int, c: Int): Int {
    if (dp[l][r][c] >= 0) return dp[l][r][c]

    fun doDPInternal(l: Int, r: Int, c: Int): Int {
      if (l == r) return 1
      if (r - l == 1) {
        return if (s[l] == s[r] || c > 0) 2 else 1
      }
      // r - l >= 2
      if (s[l] == s[r]) {
        return doDP(l + 1, r - 1, c) + 2
      } else {
        val v1 = Math.max(doDP(l + 1, r, c), doDP(l, r - 1, c))
        if (c == 0) return v1
        val v2 = doDP(l + 1, r - 1, c - 1) + 2
        return Math.max(v1, v2)
      }
    }

    val value = doDPInternal(l, r, c)
    dp[l][r][c] = value
    return value
  }

  println(doDP(0, n - 1, k))
}
