题目内容

某通信台要把一条只含小写字母的报文 $S$（长度为 $n$）拆成恰好 $m$ 个连续片段依次发出。每个片段必须非空，且按原顺序拼接后重新得到 $S$。

一个片段的干扰度，定义为该片段里出现过的不同字母个数。整次发送的干扰度，定义为这 $m$ 个片段干扰度中的最大值。

请给出一种拆分方式，使整次发送的干扰度尽可能小，并输出这个最小可能值。

输入描述

第一行两个整数 $n$、$m$。

第二行一个长度为 $n$ 的字符串 $S$，只由小写字母组成。

约束

$1 \le m \le n \le 10^5$

$S$ 只含小写字母 a～z

输出描述

输出一个整数：整次发送干扰度的最小可能值。

样例1

输入

5 2
aabbc

输出

2

说明

要拆成 $2$ 段。一种方案是 aa|bbc，两段干扰度分别为 $1$ 和 $2$，整次发送干扰度为 $2$。

若要求每段干扰度都不超过 $1$，只能拆成 aa|bb|c，至少 $3$ 段，超过 $m=2$，不可行。因此答案为 $2$。

样例2

输入

6 3
abcabc

输出

2

说明

要拆成 $3$ 段。方案 ab|ca|bc 的三段干扰度都是 $2$，整次发送干扰度为 $2$。

若上限为 $1$，每个片段只能是单一字母的连续段，最少需要 $6$ 段，超过 $m=3$，不可行。因此答案为 $2$。