Minimize the Maximum Segment

JYY wrote down a circular string S of length N containing only the 9 digits from 1 to 9. He wants to make K cuts on the circle (i.e. choose K cut points) so that the circle is partitioned into exactly K non‐empty contiguous segments. Since each segment consists solely of digits, we can treat each as a decimal number. JYY wishes to choose the cuts and the starting point of reading the circle in order to minimize the maximum among these K numbers.

More formally, let S be a circular string. For any rotation T of S (i.e. T = S[i:]+S[:i] for some 0 ≤ i < N) and any valid partition of T into exactly K non-empty segments, interpret each segment as a decimal number. Define M as the maximum among these numbers. The task is to choose a rotation and a way to partition it into K segments so that M is minimized. Output that minimum possible value of M.

Note that when a number is interpreted in decimal, it is compared using its numerical value. In order to describe any formula or inequality in our solution, we will use \( \le \) in \( \LaTeX \) format.

inputFormat

The first line contains two integers N and K (with 1 ≤ K ≤ N) separated by a space.

The second line contains the circular string S of length N, which consists only of digits '1' to '9'.

outputFormat

Output a single integer, the minimum possible value of the maximum segment number after exactly K cuts.

sample

3 2
123

12