2088. QuickSums

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string “12” (quotes for clarity). With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get “1+2”, which evaluates to 3. So, in that case, given “12”, a minimum of 1 addition is required to get the number 3. As another example, consider “303” and a target sum of 6. The best strategy is not “3+0+3”, but “3+03”. You can do this because leading zeros do not change the result.

-numbers will contain between 1 and 10 characters, inclusive.

-Each character in numbers will be a digit.

-sum will be between 0 and 100, inclusive.

输入格式

There are too many test case.First a line is a string of digits.then a target number.

输出格式

calculate and output the minimum number of additions required to create an expression from numbers that evaluates to sum. If this is impossible, output -1.

样例

Input
99999
45

Output
4
In this case, the only way to achieve 45 is to add 9+9+9+9+9. This requires 4 additions.


2 人解决，5 人已尝试。

3 份提交通过，共有 10 份提交。

9.2 EMB 奖励。