A9571. Wavy numbers

A wavy number is such positive integer that for any digit of its decimal representation except for the first one and the last one following condition holds: the digit is either strictly larger than both its adjacent digits or strictly less than both its adjacent digits. For example, numbers $35270$ , $102$ , $747$ , $20$ and $3$ are wavy and numbers $123$ , $1000$ and $2212$ 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}$ .

The only line of input contains two integers $n$ and $k$ , separated by a single space ( $1<=n,k<=10^{14}$ ).

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

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