Circle of digits
Time Limit: 10 Seconds Memory Limit: 131072 KB
You are given a circular string of length N that consists of digits '1'..'9'. You want to split it into K continuous non-empty parts. Each of those parts represents a decimal notation of some integer number. Your goal is to find a partition that minimizes the maximum integer from the partition at hand.
For example, if the string is 7654321 and K=3 then the optimal partition is: {176, 54, 32} which has 176 as the maximum number. Note that the string is cyclic, that is the first character goes right after the last one (as in the 176 part of the above example).
Input
The first line of the input contains two integers N and K (3 ≤ N ≤ 100000, 2 ≤ K ≤ N). The second line contains a string of length N which consists only of characters ‘1’..’9’.
Output
Output the value of the maximal number in the optimal partition.
Sample Input
4 2 4321 7 3 7654321 5 5 12321
Sample Output
32 176 3Submit