Escape

Interview

Time limit1sMemory limit256 MB

Summary

Find the fewest presses of A (add 1) and B (double then cut the leading digit) turning N into G without passing 99999 in T steps, or report impossible.

Level: Medium6 of 10
Topics: BFS, Graph, Bit manipulation
Solved: No attempts yet

Problem

Hongik is on the problem-setting team for the Hongik University programming contest. While writing problems at dawn, he felt a pain in the back of his head and lost consciousness.

Hongik woke up in a narrow room. Looking around, he saw a five-digit decimal number N displayed on an LED panel on the wall, and next to it the letters T and G along with two other integers. In front of the wall were two buttons, A and B.

After pressing the buttons this way and that, the clever Hongik quickly figured out how to escape the room.

What Hongik learned about the buttons and the number is as follows.

Pressing button A increases N by 1.
Pressing button B multiplies N by 2, then decreases the highest nonzero digit by 1. For example, 123 becomes 146, 5 becomes 0, and 3 becomes 5. However, if N is 0, pressing button B does not change the number.
Because the LED has only five digits, the moment N exceeds 99,999, the escape fails.
If pressing button B to multiply N by 2 makes the number exceed 99,999 at that moment, the escape fails even if decreasing the highest digit by 1 would bring it back to 99,999 or below.

Hongik also learned that he can press the buttons at most T times, and that he can escape only if he makes the number N shown on the LED equal to G within that number of presses.

In the middle of all this, the clever Hongik got his pride involved and decided to escape by pressing the buttons the minimum number of times.

Wishing Hongik luck in escaping the room, find the minimum number of button presses needed to escape.

Input

The first line gives N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), and G (0 ≤ G ≤ 99,999), separated by a single space.

N is the number shown on the LED, T is the maximum number of button presses allowed, and G is the number that must be matched to escape.

Output

On the first line, print the minimum number of button presses needed to escape.

If escape is impossible, print “ANG” without the quotes.

Examples4

Example 1
Input
```
1 7 10
```
Expected output
```
7
```
Example 2
Input
```
7142 10 7569
```
Expected output
```
3
```
Example 3
Input
```
7142 1 7569
```
Expected output
```
ANG
```
Example 4
Input
```
63429 99999 231
```
Expected output
```
ANG
```