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
3
Submit