Minimal Plus Insertions

Given a digit string S and a target integer T, determine the minimum number of plus sign insertions required such that when the string is split by these plus signs and the resulting numbers are summed, the total equals T. In each insertion, you place a plus sign (+) between two adjacent digits. Note that numbers may have leading zeros, which do not affect their value.

For example, consider the string 12:

• With 0 insertions, the value is $12$.
• With 1 insertion (i.e. 1+2), the value is $3$.

Another example: for the string 303 and target $6$, the optimal solution is 3+03, which gives $3+3=6$ instead of, for instance, 3+0+3.

inputFormat

The input consists of two lines:

1. The first line contains the digit string S.
2. The second line contains the target integer T.

outputFormat

Output a single integer representing the minimum number of plus sign insertions required to achieve the sum equal to T. If no solution exists, output -1.

sample

12
3

1