如果一个字符串从右向左读和从左向右读是一样的，那么它就是回文串。例如，“abba”、“zjcpcjz”都是回文串。Chenjb 热爱回文串，他拥有一个极长的回文串 $S$。

昨天，人民币玩家 Chenjb 花钱在某款热门手游中开启了 $m$ 个宝箱。每次他付费开启一个宝箱，都有 $0.003\%$ 的概率获得一个名为“SSR”（Specially Super Rare）的道具。每当 Chenjb 获得这样一个道具时，他就会删除字符串 $S$ 中的一个字符，或者修改字符串 $S$ 中的一个字符，以庆祝他的好运。

今天，Chenjb 希望通过从 $S$ 中删除一些字符，使他的字符串 $S$ 再次成为回文串。请编写一个程序，帮助他找到当前字符串 $S$ 的最长回文子序列的长度。

输入格式

输入仅包含一组测试数据。

第一行包含一个字符串 $S$，由 $n$ ($1 \le n \le 10^7$) 个小写英文字母组成，表示当前的字符串。

第二行包含一个整数 $m$ ($1 \le m \le 10^7$)，表示 Chenjb 昨天开启的宝箱数量。

输出格式

输出一行，包含一个整数，表示 $S$ 的最长回文子序列的长度。

样例

输入 1

abadba
31274

输出 1

5