题目描述

设有一个长度为 $N$ 的数字串，要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分，使得这 $K+1$ 个部分的乘积能够为最大。

如下有一个 $N=3$ 的数字串：$312$，

当 $K=1$ 时会有以下两种分法：

1. $3\times 12=36$

2. $31\times 2=62$

最大乘积：$31×2=62$

输入格式

第一行共有 $2$ 个自然数 $N$，$K$。

第二行是一个长度为 $N$ 的数字串。

输出格式

输出所求得的最大乘积（一个自然数）。

4 2
1231

62

9 4
321044105

5166000

数据规模与约定

$6\le N\le 40$，$1\le K\le 6$。