给你一个长度为 $N$ 的环形字符串，它仅由字符 '1' 到 '9' 组成。你需要将其划分为 $K$ 个连续的非空部分。每个部分都代表一个整数的十进制表示。你的目标是找到一种划分方案，使得划分出的所有整数中的最大值最小。

例如，如果字符串是 7654321 且 $K=3$，那么最优划分方案为：$\{176, 54, 32\}$，其中最大值为 $176$。请注意，字符串是环形的，也就是说第一个字符紧跟在最后一个字符之后（如上述例子中的 176 部分）。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$（$3 \le N \le 100000$，$2 \le K \le N$）。

第二行包含一个长度为 $N$ 的字符串，该字符串仅由字符 '1' 到 '9' 组成。

输出格式

输出最优划分方案中最大整数的值。

样例

输入样例 1

4 2
4321

输出样例 1

32

输入样例 2

7 3
7654321

输出样例 2

176

输入样例 3

5 5
12321

输出样例 3

3

说明

在第一个样例中，最优划分方案为 $\{32, 14\}$。

在第二个样例中，最优划分方案为 $\{176, 54, 32\}$。

在第三个样例中，最优（也是唯一可能的）划分方案为 $\{1, 2, 3, 2, 1\}$。