New Operator

Time limit2sMemory limit128 MB

Summary

Given digit-based functions and a custom operator @ built from them, find the minimum number of @ operations starting from X to reach target value G, or report -1.

Level: Medium7 of 10
Topics: Math, Dynamic programming, BFS, Implementation
Solved: No attempts yet

Problem

For a positive integer N, define these functions.

Sum(N) is the sum of all digits of N.
Prod(N) is the product of all digits of N.
Prod3(N) is the product of the three largest digits of N. If N has fewer than three digits, then Prod3(N) = Prod(N).
Smallest(N) is the smallest digit of N.
First(N) is the first digit of N.

For two values X and Y, define the operator @ as follows.

X @ Y = 5 * Prod3(X) + First(X) * Sum(Y) + Smallest(Y)

The following identities hold.

Sum(47) = 4 + 7 = 11
Prod(2322) = 2 * 3 * 2 * 2 = 24
Prod3(2322) = 3 * 2 * 2 = 12
Prod3(47) = Prod(47) = 4 * 7 = 28
Smallest(427) = 2
First(427) = 4
12034 @ 217 = 5 * (4 * 3 * 2) + 1 * (2 + 1 + 7) + 1 = 131

A valid expression can be formed only by the following rules.

The input value X is a valid expression.
If A and B are valid expressions, then A @ B is also a valid expression.
Any expression that cannot be formed by the rules above is not valid.

Given X and a target value G, find the minimum number of @ operators in a valid expression whose value is G. If no such expression exists, print -1.

Input

The first line contains X and G. X is a positive integer not greater than 1,000,000, and G is a positive integer not greater than 2,000,000,000.

Output

If a valid expression with value G can be formed, print the minimum number of @ operators in such an expression. Otherwise, print -1.

Examples7

Example 1
Input
```
374 659
```
Expected output
```
2
```
Example 2
Input
```
13 13
```
Expected output
```
0
```
Example 3
Input
```
374 465
```
Expected output
```
1
```
Example 4
Input
```
374 469
```
Expected output
```
2
```
Example 5
Input
```
374 1024
```
Expected output
```
8
```
Example 6
Input
```
654321 12
```
Expected output
```
10
```
Example 7
Input
```
654321 1234567
```
Expected output
```
-1
```