题目描述

NOIP 2000

古人云:"不谋万世者,不足谋一时:不谋全局者,不足谋一域。"小嘉通过研究惊奇 地发现,每个人一生的幸福指数可以用一个长度为$\red{n}$的$\red{十进制}$数字字符串来表示,并且可以. 通过全局统筹安排,将幸福指数分成$\red{k+1}$个部分应用在她感兴趣的不同领城,从而使得总 体幸福值最强,所谓幸福值最强,是指使得$\red{k+1}$个部分的乘积为最大。例如$\red{n=6,k=3,}$且 数字字符串为"$\red{310143}$"时,此时可能有的情况有下列各种:

$\red{3\times 1\times 0\times 143= 0}$

$\red{3\times 1\times 01\times 43= 129}$

$\red{3\times 1 \times 014\times 3= 126}$

$\red{3\times 10\times 1\times 43 = 1290}$

$\red{3\times 10\times 14\times 3 = 1260}$

$\red{3\times 101\times 4\times 3 = 3630}$

$\red{31\times 0\times 1\times 43 = 0}$

$\red{31\times 01 \times 4\times 3 = 372}$

$\red{310\times 1\times 4\times 3 = 3720}$

从上面的结果可以看出,最大乘积为$\red{310\times 1\times 4\times 3=3720}$。

现在的问题时,当$\red{n}$数字串和$\red{k}$给出之后,找出一种分法使其乘积为最大。

输入格式

第一行为两个整数,即$\red{n}$和$\red{k,6≤}$$\red{n≤}$$\red{10,1≤}$$\red{k≤}$$\red{6}$

第二行为数字字符串。

输出格式

一个整数,即最大乘积。

样例

输入样例

6 3
310143

输出样例

3720