408211: GYM103055 E Specially Super Rare

A string is palindromic iff it reads the same right to left as left to right. For example "abba", "zjcpcjz" are palindromes. Chenjb loves palindromes, and he owns an extremely long palindrome string $$$S$$$.

Yesterday, RMB player Chenjb paid to open $$$m$$$ boxes in a popular mobile game. Every time he pays to open a box, he will get an item called "SSR" (Specially Super Rare) with the probability of $$$0.003\%$$$. Every time Chenjb got such an item, he would either delete a character or modify a character in his own string $$$S$$$ to celebrate his luck.

Today, Chenjb wants his string $$$S$$$ to be palindrome again by removing some characters from $$$S$$$. Please write a program to help him find the longest palindromic subsequence of the current string $$$S$$$.

The input contains only a single case.

The first line contains a string $$$S$$$ which consists of $$$n$$$ ($$$1 \leq n \leq 10^7$$$) lower-case English letters, denoting the current string.

The second line contains a single integer $$$m$$$ ($$$1\leq m\leq 10^7$$$), denoting the number of boxes Chenjb opened yesterday.

Print a single line containing an integer, denoting the length of the longest subsequence of $$$S$$$.

abadba
31274

5