#P1729. 2024.3.23-MT-第四题-塔子哥切字符串

2024.3.23-MT-第四题-塔子哥切字符串

题目描述

塔子哥拿到了一个字符串，并希望将其切割成若干个连续子串，并使每个子串的权值不小于kk，请你求出最多可以切割出的子串的数量。

字符串以连续段长度给出，如：a(2)b(2)c(2)表示aabbccaabbcc

字符串权值定义为，字符串长度乘以字符种类数，例如:"arcaea"权值为6∗4=246*4=24

注意:a(2)a(2)也是合法数据

输入描述

第一行两个正整数n,k(1≤k,n≤1018)n,k(1\le k,n\le 10^{18})，代表字符串长度和连续段最小权值。

第二行一个仅包含小写字母、数字和括号的字符串，长度不超过10610^6

输出描述

如果无法切割，输出-1。否则输出最大数量。

样例

输入

7 6
a(2)b(2)a(3)

输出

2

说明

切割成aab和baaa。

输入

1000000000 5
x(1000000000)

输出

200000000

知识点:*****

查看知识点以及同类型题目

Statistics