Shortest Substring with At Least K Occurrences

You are given an integer N representing the length of a string S, an integer K, a string S of length N, and a character C. Your task is to find the length of the shortest contiguous substring of S that contains at least K occurrences of the character C. If no such substring exists, output -1.

Formally, if we denote by cnt(sub) the number of times C appears in a substring sub of S, you need to find the minimum length L such that there exists some substring sub of S with length L satisfying

or determine that no such substring exists.

Example:

Input:
10 2
abcabcabcx
a
Output:
4

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains two space-separated integers, N and K.
2. The second line contains the string S of length N.
3. The third line contains a single character C.

outputFormat

Output a single integer to standard output (stdout), representing the length of the shortest substring of S that contains at least K occurrences of C. If no valid substring exists, output -1.## sample

10 2
abcabcabcx
a

4