题目描述

给定一个长度为 $n$ 的数字串。请在其中插入 $k$ 个乘号，将它分成 $k+1$ 个部分，并使这 $k+1$ 个部分对应整数的乘积最大。

例如，数字串为 $312$，当 $n=3,k=1$ 时，有两种分法：

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

因此最大乘积为 $62$。

输入格式

第一行包含两个整数 $n$ 和 $k$。

第二行包含一个长度为 $n$ 的数字串。

输出格式

输出一行一个整数，表示最大乘积。

4 2
1231

62

样例解释

一种最优分法为 $1 \times 2 \times 31=62$。

数据范围与提示

• $1 \le k < n \le 16$