AT_agc021_d.[AGC021D] Reversed LCS

高桥君打算送给妈妈一个字符串作为礼物。

字符串 $T$ 的“价值”定义为：将 $T$ 反转得到 $T'$，$T$ 与 $T'$ 的最长公共子序列的长度。也就是说，作为子序列（不要求连续）同时出现在 $T$ 和 $T'$ 中的最长字符串的长度。

高桥君手中有一个字符串 $S$。他希望通过最多修改 $K$ 个字符，使得最终得到的字符串的“价值”尽可能大。

请你求出能够达到的最大“价值”。

输入以如下格式从标准输入读入：

$S$ $K$

输出能够达到的最大“价值”。

限制条件

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

样例解释 1

将第 $1$ 个字符修改为 c 后，字符串变为 cbcabcabc。此时，设该字符串为 $T$，则长度为 $7$ 的字符串 cbabcbc 是 $T$ 与 $T'$ 的最长公共子序列的一种。

由 ChatGPT 4.1 翻译