题目描述

小珅和小泽喜欢探险，他们早就听说在水帘岛的一个地下城里埋葬着一堆宝藏。为此，他们历时多年收集资料，终于搞清楚宝藏的位置。

小珅、小泽和探险队来到宝藏大门处，发现大门处有 $n$ 个古老的石柱，经过研究发现，需要先给这些石柱补充能量，所有石柱能量补充结束后，大门才能打开。

用 A~Z 来表示每种石柱，每种石柱充能需要 $1$ 分钟，每次只能给一个石柱充能，石柱充能的顺序小珅和小泽可以随意安排，但是需要满足以下条件：

• 相同种类的石柱充能中间需要 $k$ 分钟的冷却时间，即当前石柱到下一个相同种类的石柱之间必须要等待 $k$ 分钟，不论中间是否给其他石柱充能。
• 不同种类的石柱充能中间不需要冷却时间。

请你帮助小珅和小泽计算，最少需要多长时间才能给所有石柱完成充能，使得大门能够被打开拿到宝藏。

输入格式

第一行输入两个整数 $n,k$，分别表示石柱的数量和充能时间。

第二行输入一个长度为 $n$ 的字符串 $s$，字符串只包含大写英文字母 A~Z，表示石柱的种类。

输出格式

输出一个整数，表示给所有石柱完成充能所需要的最少时间。

6 2
TTTXXX

8

6 0
TTTXXX

6

12 2
AAAAAABCDEFG

16

说明提示

样例 $1$ 中，可以按照 T → X → 等待 → T → X → 等待 → T → X 的顺序完成充能，共需要 $8$ 分钟。第一次给 T 充能到第二次给 T 充能之间，虽然给 X 充能花费了 $1$ 分钟，但相同种类的石柱之间仍然需要等待 $2$ 分钟。

样例 $2$ 中，$k=0$，可以按照任意顺序完成充能，共需要 $6$ 分钟。

样例 $3$ 中，可以按照 A → B → C → A → D → E → A → F → G → A → 等待 → 等待 → A → 等待 → 等待 → A 的顺序完成充能，共需要 $16$ 分钟。

数据范围

• 对于 $10\%$ 的数据，保证所有石柱的种类互不相同；
• 对于另外 $10\%$ 的数据，保证 $k=0$；
• 对于另外 $20\%$ 的数据，保证每种石柱的数量都相同；
• 对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\le k\le 1000$，字符串 $s$ 只包含大写英文字母 A~Z。

1 1000
A

1

6 0
TTTXXX

6