Wavy numbers

题面翻译

题目描述

我们将一类正整数称为“波浪数”，它的每个数位上的数都大于或小于两边数位上的数。例如，$35270$，$102$，$747$，$20$ 和 $3$ 都是波浪数；而 $123$，$1000$ 和 $2212$ 不是波浪数。

你的任务是找到第 $k$ 小且能被 $n$ 整除的波浪数 $r$。

保证 $r \le 10^{14}$。

输入格式

输入仅有一行，包含两个整数 $n$ 和 $k$（$1 \le n,k \le 10^{14}$） 。

输出格式

输出问题的答案 $r$，如果答案不存在或大于 $10^{14}$，则输出-1。

说明/提示

第一个样例中，前四个能被 $n$ 整除的波浪数为：$492$，$615$，$738$ 和 $1845$。

题目描述

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.

样例 #1

样例输入 #1

123 4

样例输出 #1

1845

样例 #2

样例输入 #2

100 1

样例输出 #2

-1

样例 #3

样例输入 #3

97461 457

样例输出 #3

1805270103

提示

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