Bessie is playing a video game! In the game, the three letters ' ', ' ', and ' ' are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only distinct combos possible ( ). Combo i is represented as a string which has a length between and and contains only the letters ' ', ' ', and ' '. Whenever Bessie presses a combination of letters that matches with a combo, she gets one point for the combo. Combos may overlap with each other or even finish at the same time! For example if and the three possible combos are " ", " ", and " ", and Bessie presses " ", she will end with points. Bessie may score points for a single combo more than once. Bessie of course wants to earn points as quickly as possible. If she presses exactly buttons ( ), what is the maximum number of points she can earn?
题意简述:给出 个 串 和 ，现要求生成一个长 的字符串 ，问 与 的最大匹配数
输入格式
Line : Two space-separated integers: and .
Lines : Line contains only the string , representing combo .
输出格式
Line : A single integer, the maximum number of points Bessie can obtain.
样例
样例输入 #1
3 7 ABA CB ABACB
样例输出 #1
4
数据范围与提示
The optimal sequence of buttons in this case is , which gives points-- from , from , and from .
