题目描述

给定一个只包含数字的字符串，长度为 N（ 5 ＜ N ≤ 20 ），和一个正整数 M（ 1 ≤ M ≤ 5 ）。使用 M 个乘号插入到字符串中，且两个乘号不能相邻，插入后，生成一个乘法算式。找出一种使乘法算式数值最大的插入方式，并将结果输出。（乘号不能放在字符串的首尾位置）

如字符串为 123456，插入 2 个乘号。插入方式有：

1: 1*2*3456=6912
2: 1*23*456=10488
3: 1*234*56=13104
4: 1*2345*6=14070
5: 12*3*456=16416
6: 12*34*56=22848
7: 12*345*6=24840
8: 123*4*56=27552
9: 123*45*6=33210
10: 1234*5*6=37020

其中乘法算式数值最大是第十种，为 37020 。

输入格式

第一行输入两个正整数 N（ 5 ＜ N ≤ 20 ），M（ 1 ≤ M ≤ 5 ），N 表示字符串长度，M 代表乘号个数，两个正整数之间一个空格隔开。

第二行输入一个长度为 N，且只包含数字的字符串，表示要插入 M 个乘号的字符串

输出格式

输出一个整数，表示最大的结果。

样例

6 2
123456

37020

2022 年 3 月 13 日 STEMA