306008 - 乘积最大

将一个长度为n的十进制数字字符串分成k+1个部分,使得k个部分的乘积为最大。例如n=6,k=3,且数字字符串为“310143”时,此时可能有的情况有下列各种:

3×1×0×143=0

3×1×01×43=129

3×1×014×3=126

3×10×1×43=1290

3×10×14×3=1260

3×101×4×3=3630

31×0×1×43=0

31×01×4×3=372

310×1×4×3=3720

从上面的结果可以看出,最大乘积为310×1×4×3=3720

输入

第一行为两个整数,即n,k(6≤n≤40,1≤k≤6)

第二行为数字字符串。

输出

一个整数,即最大乘积。

样例

输入

6 3
310143

输出

3720
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题