塔子哥拿到了一个字符串,并希望将其切割成若干个连续子串,并使每个子串的权值不小于k,请你求出最多可以切割出的子串的数量。
字符串以连续段长度给出,如:a(2)b(2)c(2)表示aabbcc
字符串权值定义为,字符串长度乘以字符种类数,例如:"arcaea"权值为6∗4=24
注意:a(2)a(2)也是合法数据
第一行两个正整数n,k(1≤k,n≤1018),代表字符串长度和连续段最小权值。
第二行一个仅包含小写字母、数字和括号的字符串,长度不超过106
如果无法切割,输出-1。否则输出最大数量。
输入
7 6
a(2)b(2)a(3)
输出
2
说明
切割成aab和baaa。
输入
1000000000 5
x(1000000000)
输出
200000000
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.