시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB242225.000%

문제

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).

입력

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 the value of the maximal number in the optimal partition.

 

예제 입력 1

4 2
4321

예제 출력 1

32

예제 입력 2

7 3
7654321

예제 출력 2

176

예제 입력 3

5 5
12321

예제 출력 3

3

힌트

In the first sample the optimal partition is {32, 14}.

In the second sample the optimal partition is {176, 54, 32}.

In the third sample the optimal (and the only possible) partition is {1, 2, 3, 2, 1}.