Sammy's String Partition

Sammy the squirrel has found a string S of length N. He wishes to divide this string into exactly K contiguous substrings such that the maximum length among these substrings is minimized. Your task is to help Sammy determine the minimum possible maximum substring length after optimal division.

In other words, if the string is partitioned into K contiguous parts, you need to compute the smallest integer M such that it is possible to split the string into segments where no segment has length greater than M. It is guaranteed that such a division is always possible.

Note: Even if a valid division yields fewer than K substrings, you are allowed to further split any contiguous segment arbitrarily into smaller pieces as long as the maximum length does not exceed M.

inputFormat

The input is given via stdin and consists of two lines:

1. The first line contains two space-separated integers: N (the length of the string) and K (the exact number of substrings).
2. The second line contains the string S of length N.

outputFormat

Output a single integer representing the minimum possible value for the maximum length of the K contiguous substrings after optimal division. The result should be printed to stdout.

## sample

10 3
abcdefghij

4

</p>