题目描述

给定一个长为 $n$ 的环形字符串，仅包含数字 $1$ 到 $9$。将其分成 $k$ 个部分，要求分出来的 $k$ 个数字，最大值最小化。

输入格式

输入的第一行包含两个整数 $n,k$，意义见题目描述。
输入的第二行包含一个字符串，从一个字符出发，绕题目描述中的环形字符串一周后得到的字符串。

输出格式

输出一个整数，为最大值的最小可能值。

4 2
4321

32

7 3
7654321

176

5 5
12321

3

样例说明

对于第一个样例，最优的划分是 $\{\texttt{32},\texttt{14}\}$；
对于第二个样例，最优的划分是 $\{\texttt{176},\texttt{54},\texttt{32}\}$；
对于第三个样例，最优（且唯一）的划分是 $\{\texttt 1,\texttt 2,\texttt 3,\texttt 2,\texttt 1\}$。

数据规模与约定

对于 $100\%$ 的数据，有 $3\le n\le 10^5$，$2\le k\le n$。

题目来源

SouthEastern European Regional Contest 2014, Problem B