题目描述

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

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

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

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

输入格式

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

$S$ $K$

输出格式

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

样例 1

输入

abcabcabc
1

输出

7

样例 2

输入

atcodergrandcontest
3

输出

15

说明/提示

限制条件

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

样例解释 1

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

由 ChatGPT 4.1 翻译