题目描述

在“2000—世界数学年”暨华罗庚先生诞辰 90 周年之际，江苏金坛举办了一场数学智力竞赛。你的好友 XZ 参加了比赛，其中有一道题如下：

给定一个长度为 $N$ 的数字串，要求使用 $K$ 个乘号将其分成 $K+1$ 个连续的部分，求一种划分方式，使得这 $K+1$ 个部分所形成的乘积最大。

例如：数字串 312，当 $N=3$、$K=1$ 时，有两种分法：

1. $3 \times 12 = 36$
2. $31 \times 2 = 62$

最大乘积为 $62$。

请你编写程序求出最大乘积。

输入格式

输入共两行：

• 第一行包含两个自然数 $N, K$（$2 \le N \le 40$，$1 \le K \le 6$）。
• 第二行是一个长度为 $N$ 的数字串。

输出格式

输出一个自然数，即可以得到的最大乘积。

输入输出样例 #1

输入 #1

4 2
1231

输出 #1

62

说明/提示

数字串中不会出现非数字字符；分割出的每部分按正常整数解释进行乘积计算。