Description

Given a numeric string, make it equal to a given target number using the minimum number of additions. Each addition means inserting a plus sign at some position in the string. After all required plus signs are inserted, evaluate it as ordinary addition.

For example, consider the string 12. With $0$ additions, we get the number $12$. If we insert $1$ plus sign, we get $3$. Therefore, in this case, the minimum number of additions to obtain the number $3$ is $1$.

Another example: consider the string 303 and the target number $6$. The optimal way is not 3+0+3, but 3+03. This works because a leading $0$ in a number does not change its value.

Input Format

The first line: a string $s$.

The second line: an integer $n$.

Output Format

Output a single integer on one line, the minimum number of additions to make $s$ equal to $n$. If it is impossible to make $s$ equal to $n$, output $-1$.

99999
45

4

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le \operatorname{len}(s) \le 40$, $1 \le n \le 10^5$.

Translated by ChatGPT 5