高桥决定给他母亲一根字符串。

字符串T的值是T和T'最长公共子序列的长度，其中T'是通过反转T获得的字符串。

高桥有一个字符串s(长度<=300)。他想给她母亲一个可能值最高的字符串，所以他想将s中最多k(k<=s)个字符更改为任何其他字符，以获得可能值最高的字符串。找到可能达到的最高值。

输入：

第一行是字符串s(由小写英文字母组成)

第二行是一个整数k

输出：

可能达到的最大值