题目描述

高橋君はお母さんに文字列をプレゼントすることにしました。

文字列 $T$ の価値とは、$T$ を逆から読んだものを $T'$ として、$T$ と $T'$ の最長共通部分列の長さです。 すなわち、(連続するとは限らない)部分列として $T$ と $T'$ の両方に現れるものの最大長です。

高橋君は、文字列 $S$ を持っています。お母さんにできるだけ価値の高い文字列をプレゼントしたい高橋君は、 $S$ の文字を $K$ 箇所まで任意に変更して、できるだけ価値の高い文字列を作りたいです。

達成できる価値の最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$ $K$

输出格式

達成できる価値の最大値を出力せよ。

题目大意

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

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

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

输入：

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

第二行是一个整数k

输出：

可能达到的最大值

abcabcabc
1

7

atcodergrandcontest
3

15

提示

制約

• $1\ \leq\ |S|\ \leq\ 300$
• $0\ \leq\ K\ \leq\ |S|$
• $S$ は英小文字からなる
• $K$ は整数である

Sample Explanation 1

$1$ 文字目を c に変更すると、文字列は cbcabcabc になります。 できた文字列を $T$ とおけば、長さ $7$ の文字列 cbabcbc が $T$ と $T'$ の最長共通部分列の一例となります。