2151: 宝典2第十一章添加号问题

【题目描述】添加号问题（parentheses.cpp/c/pas）

天顶星人善于用种种方式引诱人心的堕落，例如傲慢、妒忌、暴怒、懒惰、贪婪、恐惧、猜疑、功利等，但多数人对此一无所知，却把由此而引起的一些负面影响称之为走了霉运，甚至有魔法师宣称每个人的霉运指数可以表示为一个由数字1，2，…，9组成的数字串（长度不超过200）。虽然霉运是不可避免的，但是张琪曼发现，可以通过巧妙的方法如积极向上的心态使霉运值减到最低。抽象到数学模型，就是如何将M(M≤20)个加号(“+”)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。

注意加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。

M保证小于数字串的长度。

例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。

【输入格式】

数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。

【输出格式】

在屏幕上输出所求得的最小和的精确值。

【输入样例】

79846

2

【输出样例】

133