You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

辰辰迷上了字符串的子串，$k$ 是辰辰的幸运数字，于是就有了下面的问题。

Description

定义一个字符串 $s$ 中，出现次数最多的长度为 $k$ 的子串（连续的子序列）为 $s$ 的 $k$-String。

给定一个仅包含 大 写字母的字符串 $s$，求 $s$ 的 $k$-String 出现的次数。

Input

输入共 $2$ 行。

• 第 $1$ 行：$1$ 个字符串。
• 第 $2$ 行：$1$ 个正整数 $k$。

ouTput

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

Samples

AAAAA
1

5

对于这个字符串，$1$ 个字符组成的子串只有 A，共出现 $5$ 次，所以答案为 $5$。

ACTCACTC
4

2

$4$ 个字符组成的子串为：ACTC，CTCA，TCAC 与 CACT。其中 ACTC 出现 $2$ 次，其余均出现 $1$ 次，所以出现最多的次数为 $2$，即为答案。

Limitation

特殊性质：字符串的每个字符都相同。

提示：std::unordered_map，string::substr