[JSOI2015] 串分割
题目背景
JYY 每天都会在地铁上度过很长的时间。
为了打发时间,JYY 随手写下了一个很长的环形的数字字符串,并且陷入了沉思。
题目描述
JYY 写下了一个长度为 $N$ 的,仅包含 `1`,`2`,……,`9` 这 $9$ 种不同字符的环形字符串 $S$。JYY 希望把 $S$ 进行 $K$ 次切割,并分成 $K$ 个非空的子串。对于每一个子串,由于其仅包含数字,我们可以将其看成一个十进制数——因此
经过 $K$ 次切割,JYY 可以得到 $K$ 个不同的十进制数。JYY 希望他得到的这 $K$ 个数中,最大的那一个尽量小。
输入输出格式
输入格式
第一行包含两个整数 $N$ 和 $K$。
第二行包含一个长度为 $N$ 的字符串 $S$。
输出格式
输出一行包含一个正整数,表示最佳分割方案中,JYY 所得到的那 $K$ 个数中,最大的那一个。
输入输出样例
输入样例 #1
4 2
4321
输出样例 #1
32
说明
对于 $100\%$ 的数据,$3\leq N\leq 2\times 10^5$,$2\leq K\leq N$。