题目描述

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

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

分法有两种

3∗12=36

31∗2=62

最大值为 62

输入格式

输入共两行

第一行，正整数 N 和 K

第二行，一个数字串

输出格式

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

样例

3 1
312

62

7 3
3314245

278040

数据规模与约定

• $2≤N≤30$
• $1≤K≤10$

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

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