P6095 [JSOI2015] String Splitting.

JYY spends a long time on the subway every day. To kill time, JYY casually wrote down a very long circular numeric string, and fell into deep thought.

JYY wrote a circular string $S$ of length $N$ that contains only the $9$ different characters `1`, `2`, $\ldots$, `9`. JYY wants to cut $S$ exactly $K$ times, splitting it into $K$ non-empty substrings. For each substring, since it contains only digits, we can treat it as a decimal number. Therefore, after $K$ cuts, JYY can obtain $K$ different decimal numbers. JYY wants the largest among these $K$ numbers to be as small as possible.

The first line contains two integers $N$ and $K$. The second line contains a string $S$ of length $N$.

Output one line containing a positive integer, which is the minimum possible value of the largest number among the $K$ numbers obtained in an optimal splitting plan.

For $100\%$ of the testdata, $3\leq N\leq 2\times 10^5$, $2\leq K\leq N$. Translated by ChatGPT 5