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 翻译