[Jsoi2015]串分割

时间限制:30s      空间限制:512MB

题目描述

【故事背景】
JYY每天都会在地铁上度过很长的时间。为了打发时间,JYY随手写下了一个很长的环形的数字字符串,并且陷入了沉思。
【问题描述】
JYY写下了一个长度为N的,仅包含‘1’,‘2’,……,‘9’,这9种不同字符的环形字符串S。
JYY希望把S进行K次切割,并分成K个非空的子串。对于每一个子串,由于其仅包含数字,我们可以将其看成一个十进制数——因此经过K次切割,JYY可以得到K个不同的十进制数。
JYY希望他得到的这K个数中,最大的那一个尽量小。


输入格式

输入文件的第一行包含两个整数N和K;
第二行包含一个长度为N的字符串S。N < =  200,000, 2 < =  K < =  N3 < = N < = 200,000, 2 < = K < = N


输出格式

输出一行包含一个正整数,表示最佳分割方案中,JYY所得到的那K个数中,最大的那一个。


样例输入

4 2
4321

样例输出

32

提示

 3 < = N < = 200,000, 2 < = K < = N


题目来源

By 佚名上传