题目描述

给出一个只包含A, G, C, T的字符串, 计算长度为 $k$ 的子串中出现次数最多的子串出现的次数。

输入格式

两行，第一行为一个字符串，保证字符串只含有 A, G, C, T 四种字符；

第二行为一个正整数 k，意义与题目描述相同。

输出格式

一行，一个正整数，为题目描述中所求答案。

样例

样例输入1

AAAAA
1

样例输出1

5

样例输入2

ACTCACTC
4

样例输出1

2

数据范围与提示

记字符串的长度为 $n$。

本题共10组数据，只有输出与标准输出一致才可以获得该测试点的分数。

下面给出每组数据的范围和满足性质情况：

性质：给出的字符串中每个字符均相同。

对于所有数据均保证 $k<=n$