题目描述

Takahashi 决定给他的母亲一个字符串。

定义一个字符串 $T$ 的 value 为 $T$ 和 $T'$（$T'$ 是将 $T$ 反转得到的字符串）的最长公共子序列的长度。也就是说，value 是以下两个字符串相等的最长长度：$T$ 的一个子序列（可以非连续），和 $T'$ 的一个子序列（可以非连续）。

Takahashi 有一个字符串 $S$。他想给他的母亲一个尽可能高的 value 值的字符串，因此他希望在 $S$ 中至多更改 $K$ 个字符，以便获得一个尽可能高的 value 值的字符串。找到可达到的最高 value 值。

约束条件

• $1 \leq |S| \leq 300$
• $0 \leq K \leq |S|$
• $S$ 由小写英文字母组成。
• $K$ 是一个整数。

输入

从标准输入读入输入数据，格式如下：

$S$ $K$

输出

输出可达到的最高 value 值。

示例输入 1

abcabcabc
1

示例输出 1

7

将第一个字符改为 c 得到 cbcabcabc。令这个字符串为 $T$，$T$ 和 $T'$ 的一个最长公共子序列是 cbabcbc，长度为 $7$。

示例输入 2

atcodergrandcontest
3

示例输出 2

15