配点 : $900$ 点

問題文

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

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

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

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

制約

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

入力

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

$S$

$K$

出力

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

abcabcabc
1

7

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

atcodergrandcontest
3

15