题目背景

第十三届蓝桥STEMA青少年组2022年3月C++组第5题

题目描述

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

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

$1*2*3456=6912, 1*23*456=10488$,

$1*234*56=13104, 1*2345*6=14070$,

$12*3*456=16416, 12*34*56=22848$,

$12*345*6=24840, 123*4*56=27552$,

$123*45*6=33210, 1234*5*6=37020$

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

输入格式

第一行输入一个正整数 $m（1≤m≤5）$，表示乘号个数。 第二行输入一个只包含数字的字符串$（5<字符串长度≤20）$，表示要插入 m 个乘号的字符串。

输出格式

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

样例 #1

样例输入 #1

2
123456

样例输出 #1

37020

提示

本题保证最终成绩的结果不超过 long long 的最大范围，因此不需要使用高精度算法。