题目描述

输入一个长度为 $N$ 的数字串， 用 $K$ 个乘号将它分为 $(K+1)$ 个部分，使得得到的乘积最大

例如 $N = 3$ , $K = 1$ ，输入的数字串为 312

分法有两种

$3 * 12 = 36$

$31 * 2 = 62$

最大值为 $62$

输入格式

输入共两行

第一行，正整数 $N$ 和 $K$

第二行，一个数字串

输出格式

用 $K$ 个乘号将数字串划分为 $K+1$ 个部分所得到的最大乘积

样例

样例输入1

3 1
312

样例输出1

62

样例输入2

7 3
3314245

样例输出2

278040

数据范围与提示

$2 \le N \le 30$

$1 \le K \le 10$

温馨提示：本题不需要额外写高精度，用 long long 即可.

（改编自2000年全国NOIP提高组试题）