Lazy 收集了一大瓶弹珠，用它玩祖玛。弹珠有 26 种颜色，用大写字母 A...Z 表示。他把这堆弹珠排在无限长直轨道上。为了降低游戏的难度，他决定通过一些交换，构造出一段最长的同色的弹珠。Lazy 非常的懒，他至多只愿意交换 N 次，每次交换，他会交换相邻的两个弹珠。求能得到的最长的同色弹珠有多长.

第一行，一个字符串，仅包含大写字母，表示弹珠的颜色；

第二行，一个整数 N，表示最多交换的次数

一行一个整数，表示最长的同色弹珠。

样例一：ABBABABBA 通过 3 次交换，可得到 ABBBBAABA

对于 50%数据，字符串长度 l<=50

对于 100%数据，字符串长度 l<=5000,n<=25000000