J18 例题-5 乘积最大

题目描述

设有一个长度为 $N$ 的数字串，要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分，找出一种分法，使得这 $K+1$ 个部分的乘积能够为最大。 如下的一个例子： 有一个数字串：$312$， 当 $N=3$，$K=1$ 时会有以下两种分法： 1）$3 \times 12=36$ 2）$31 \times 2=62$ 这时，符合题目要求的结果是: $31 \times 2 = 62$ 请你设计一个程序，求得正确的答案。

输入格式

共有两行： 第一行共有 $2$ 个自然数 $N,K$ ； 第二行是一个长度为 $N$ 的数字串。

输出格式

一个整数，表示所求得的最大乘积。

样例输入

4  2
1231

样例输出

62

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据有 $6 \le N \le 16,1 \le K \le 6$ 。