Circle of digits

Time limit5sMemory limit256 MB

Summary

Split the circular digit string into K contiguous parts so the largest part value is as small as possible, and output that value.

Level: Medium7 of 10
Topics: Binary search, Dynamic programming, String matching
Solved: No attempts yet

Problem

A circular string of length $N$ consists of the digits '1' to '9'. Split it into $K$ continuous non-empty parts. Each part is the decimal notation of one integer. Find the partition that makes the largest of those integers as small as possible, and report that largest integer.

For example, if the string is 7654321 and $K = 3$ , the optimal partition is {176, 54, 32} and its largest number is 176. The string is circular, so the first character follows the last one. The part 176 in this example is built that way.

Input

The first line contains two integers $N$ and $K$ ( $3 \le N \le 100000$ , $2 \le K \le N$ ). The second line contains a string of length $N$ that consists only of the characters '1' to '9'.

Output

Print the largest number of the optimal partition.

Hint

For the string 4321 with $K = 2$ , the optimal partition is {32, 14}. For the string 7654321 with $K = 3$ , it is {176, 54, 32}. For the string 12321 with $K = 5$ , only one partition exists, {1, 2, 3, 2, 1}.

Examples3

Example 1
Input
```
4 2
4321
```
Expected output
```
32
```
Example 2
Input
```
7 3
7654321
```
Expected output
```
176
```
Example 3
Input
```
5 5
12321
```
Expected output
```
3
```