题目内容

档案室新上了一台高速扫描工位，当天要处理一批纸质单据。工位只认 26 种单据类型，分别用大写字母 A 到 Z 标记。排班员拿到一份长度为 $P$ 的类型序列，每个位置对应一张单据，同一类型可以出现多次。工位每个单位时间可以处理恰好一张单据，也可以空转一个单位时间不处理任何单据。

设备手册规定：同一种类型相邻两次处理之间，必须隔开长度为 $G$ 的冷却窗口。也就是说，若某张类型为 $c$ 的单据在时刻 $x$ 处理完毕，则下一张同类型单据最早只能排在时刻 $x+G+1$。冷却窗口内可以安排其他类型，也可以空转。

单据的处理次序可以任意重排，不必保持输入顺序。求处理完所有单据所需的最短时间。

输入描述

第一行一个整数 $P$（$1\le P\le 10^4$），表示单据张数。

第二行一个长度为 $P$ 的字符串，仅由大写字母 A 到 Z 组成，第 $i$ 个字符表示第 $i$ 张单据的类型。

第三行一个整数 $G$（$0\le G\le 10^2$），表示同类单据之间的冷却长度。

输出描述

输出一个整数，表示处理完全部单据的最短时间。

样例1

输入

1
Z
5

输出

1

说明

只有一张类型 Z 的单据。不存在「下一次同类」，冷却不起作用，最短时间为 1。

样例2

输入

6
CCCDDD
3

输出

10

说明

C 与 D 各出现 3 次，冷却长度为 3。先把出现最多次的类型按冷却拉开：

C _ _ _ C _ _ _ C

空位用 D 填入后得到

C D _ _ C D _ _ C D

长度为 10。无法更短：两个最多种类都要各处理 3 次，最后一轮会并排放下 C 和 D。

样例3

输入

5
EEEEE
0

输出

5

说明

冷却长度为 0，同类可以紧挨着处理，最短时间等于单据张数 5。

数据范围

• $1\le P\le 10^4$
• $0\le G\le 10^2$
• 类型字符串只含大写字母 A–Z，长度为 $P$
• 所有输入均为整数或上述字符