Wavy Numbers

A wavy number is a positive integer that for any digit of its decimal representation, the following condition holds: The digit is either strictly larger than all adjacent digits or strictly smaller than all adjacent digits. For example, numbers $$35270$$, $$102$$, $$747$$, $$20$$ and $$3$$ are wavy but numbers $$123$$, $$1000$$, $$2212$$, and $$55$$ are not.

The task is to find the $$k^{th}$$ smallest wavy number $$r$$ that is divisible by $$n$$, for the given integer values $$n$$ and $$k$$.

You are to write a program that will find the value of $$r$$ if it doesn't exceed $$10^{14}$$.

Input format

The only line of input contains two integers $$n$$ and $$k$$, separated by a single space.

Output format

Output a single integer $$r$$ — the answer to the given problem. If such a number does not exist or it is larger than $$10^{14}$$, then print "-1" (negative one without the quotes) instead.

Limits

$$1 \leq n, k \leq 10^{14}$$.
1 11 $$n = 1$$
2 13 $$n \leq 10000$$
3 15 $$n \leq 300000$$

Samples

 Sample Input 1 Sample Output 1 123 4 1845

The values of the first four wavy numbers that are divisible by $$123$$ are: $$492$$, $$615$$, $$738$$ and $$1845$$.

 Sample Input 2 Sample Output 2 100 1 -1

 Sample Input 3 Sample Output 3 97461 457 1805270103

Compile Errors

Time Limit: 1.5 Seconds
Memory Limit: 1024MB
No. of ACs: 5