Problem: 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 1014.

Input

The only line of input contains two integers n and k, separated by a single space (1 ≤ n, k ≤ 1014). 

Output

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 1014, then print "-1" (minus one without the quotes) instead.

Examples

Input

123 4


Output

1845


Input

100 1


Output

-1


Input

97461 457


Output

1805270103

Note

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long Lim = 1e14 + 5;
const int N = 50005;
const int M = 10000000;
long long n, K;
vector<pair<int, int> > V[10][2];
bitset<M> a;
int f[M];
void upMin(int &x, int y) {
  if (x > y) x = y;
}
void upMax(int &x, int y) {
  if (x < y) x = y;
}
int cal(int x, int y, long long re, long long &K) {
  if (re >= M) return -1;
  int id1 = lower_bound(V[x][y].begin(), V[x][y].end(), make_pair((int)re, 0)) -
            V[x][y].begin();
  int id2 =
      lower_bound(V[x][y].begin(), V[x][y].end(), make_pair((int)re + 1, 0)) -
      V[x][y].begin();
  if (id2 - id1 < K) {
    K -= id2 - id1;
    return -1;
  }
  int i;
  for (i = id1; i < V[x][y].size(); i++) {
    K--;
    if (K == 0) return V[x][y][i].second;
  }
  return -1;
}
long long get() {
  if (n > Lim / K) return -1;
  int i;
  for (i = 1; i < M; i++) {
    if (i / 10 % 10 == i % 10) continue;
    int ff = i / 10 % 10 < i % 10 ? 1 : -1;
    if (i < 10 || a[i / 10] && f[i / 10] != ff) {
      if (i < 10) ff = 0;
      a[i] = 1;
      f[i] = ff;
      if (i % n == 0) {
        if (--K == 0) return i;
      }
    }
  }
  int b[15];
  memset(b, 0, sizeof(b));
  for (i = 1; i < M; i++) {
    b[0]++;
    int now = 0;
    while (b[now] == 10) {
      b[now] = 0;
      b[now + 1]++;
      now++;
    }
    int j;
    for (j = 1; j <= 5; j++)
      if ((b[j] - b[j - 1]) * (b[j] - b[j + 1]) <= 0) break;
    if (j <= 5) continue;
    V[b[6]][b[6] < b[5] ? 1 : 0].push_back(make_pair(i % n, i));
  }
  int j;
  for (i = 0; i < 10; i++)
    for (j = 0; j < 2; j++) sort(V[i][j].begin(), V[i][j].end());
  for (int x = 1; x < M; x++)
    if (a[x]) {
      int flag = 0;
      if (x >= 10) {
        if (x / 10 % 10 < x % 10)
          flag = 1;
        else
          flag = -1;
      }
      long long re = n - (long long)x * M % n;
      if (re == n) re = 0;
      if (flag != -1) {
        for (j = 0; j < x % 10; j++) {
          int s = cal(j, 1, re, K);
          if (s != -1) return (long long)x * M + s;
        }
      }
      if (flag != 1) {
        for (j = x % 10 + 1; j < 10; j++) {
          int s = cal(j, 0, re, K);
          if (s != -1) return (long long)x * M + s;
        }
      }
    }
  return -1;
}
int main() {
  cin >> n >> K;
  long long ans = get();
  cout << ans;
  return 0;
}