/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 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
出力
達成できる価値の最大値を出力せよ。
入力例 1
abcabcabc 1
出力例 1
7
1 文字目を c に変更すると、文字列は cbcabcabc になります。
できた文字列を T とおけば、長さ 7 の文字列 cbabcbc が T と T' の最長共通部分列の一例となります。
入力例 2
atcodergrandcontest 3
出力例 2
15
Score : 900 points
Problem Statement
Takahashi has decided to give a string to his mother.
The value of a string T is the length of the longest common subsequence of T and T', where T' is the string obtained by reversing T. That is, the value is the longest length of the following two strings that are equal: a subsequence of T (possibly non-contiguous), and a subsequence of T' (possibly non-contiguous).
Takahashi has a string S. He wants to give her mother a string of the highest possible value, so he would like to change at most K characters in S to any other characters in order to obtain a string of the highest possible value. Find the highest possible value achievable.
Constraints
- 1 \leq |S| \leq 300
- 0 \leq K \leq |S|
- S consists of lowercase English letters.
- K is an integer.
Input
Input is given from Standard Input in the following format:
S K
Output
Print the highest possible value achievable.
Sample Input 1
abcabcabc 1
Sample Output 1
7
Changing the first character to c results in cbcabcabc.
Let this tring be T, then one longest common subsequence of T and T' is cbabcbc, whose length is 7.
Sample Input 2
atcodergrandcontest 3
Sample Output 2
15