wavynumbers

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}\).
Subtask # Score Constraints
1 11 \(n = 1\)
2 13 \(n \leq 10000\)
3 15 \(n \leq 300000\)
4 61 No additional constraints

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


Submitting .cpp to 'wavynumbers'


You're not logged in! Click here to login

Time Limit: 1.5 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Codeforces 273E

Subtask Score
1 11
2 13
3 15
4 61
5 0