[NOI1996]添加号

Grade Open Time Friday, 19 September 2014, 10:04 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:04 am
Allow late Yes Close Time Friday, 26 September 2014, 10:04 am
Input file exam4.in Output file exam4.out

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

【输入格式】
     数字串在输入文件的第一行行首(数字串中间无空格且不折行),M的值在输入文件的第二行行首。

【输出格式】
     输出所求得的最小和的精确值。

【输入输出样例】
 
输入:
exam4.in
82363983742
3

输出:
exam4.out
2170