添加号

【问题描述】

有一个由数字 $1 ， 2 ， ... ， 9$ 组成的数字串（长度不超过 $200$ ），问如何将 $M(M\leq20)$ 个加号 "$+$"插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。 注意： 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。 $M$ 保证小于数字串的长度。 例如：数字串 $79846$ ，若需要加入两个加号，则最佳方案为 $79+8+46$ ，算术表达式的值 $133$ 。

【输入格式】

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

【输出格式】

输出所求得的最小和的精确值。

【输入样例】

82363983742
3

【输出样例】

2170