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 int MAX = 1e6 + 5;
const int mod = 1e9 + 7;
const long long INF = 1e14;
long long Ci10(int n, int jie) {
  long long ans = (long long)n;
  for (int i = 0; i < jie; i++) {
    ans = ans * 10;
  }
  return ans;
}
int check(long long m) {
  int n = 0, a[20];
  for (int i = 0; m; i++) {
    a[n++] = m % 10;
    m /= 10;
  }
  for (int i = 2; i < n; i++) {
    if ((a[i] - a[i - 1]) * (a[i - 1] - a[i - 2]) >= 0) return 0;
  }
  return 1;
}
long long wavy[MAX], nwavy = 0;
void dfs(int i, int num, int last, int up) {
  if (i >= 7) return;
  if (up == -1) {
    for (int j = 0; j < last; j++) {
      long long newnum = Ci10(j, i) + num;
      if (j) wavy[nwavy++] = newnum;
      dfs(i + 1, newnum, j, -up);
    }
  } else {
    for (int j = last + 1; j < 10; j++) {
      int newnum = Ci10(j, i) + num;
      wavy[nwavy++] = newnum;
      dfs(i + 1, newnum, j, -up);
    }
  }
}
void init_wavyNum() {
  for (int i = 0; i < 10; i++) {
    if (i) wavy[nwavy++] = i;
    dfs(1, i, i, 1);
    dfs(1, i, i, -1);
  }
}
long long bei[MAX], yushu[MAX][2][10];
map<int, int> Mp;
int main() {
  long long n, k;
  scanf("%I64d%I64d", &n, &k);
  if (n % 100 == 0 || n * k >= INF) {
    printf("-1\n");
    return 0;
  }
  if (n > 10000000) {
    long long m = 0;
    while (m < INF && k) {
      m = m + n;
      if (check(m)) k--;
    }
    if (k)
      printf("-1\n");
    else
      printf("%I64d\n", m);
    return 0;
  }
  init_wavyNum();
  sort(wavy, wavy + nwavy);
  long long cnt = 0;
  for (int i = 0; i < nwavy; i++) {
    if (wavy[i] % n == 0) bei[cnt++] = wavy[i];
  }
  if (cnt >= k) {
    printf("%I64d\n", bei[k - 1]);
  } else {
    memset(yushu, 0, sizeof(yushu));
    int ct = 1;
    for (int i = 22659; i < nwavy; i++) {
      if (wavy[i] < 100000) continue;
      if (wavy[i] >= 100000 && wavy[i] < 1000000) {
        if (wavy[i] / 100000 > (wavy[i] / 10000) % 10) {
          if (Mp[wavy[i] % n] == 0) Mp[wavy[i] % n] = ct++;
          yushu[Mp[wavy[i] % n]][0][0]++;
        }
      } else {
        if (wavy[i] / 1000000 > (wavy[i] / 100000) % 10) {
          if (Mp[wavy[i] % n] == 0) Mp[wavy[i] % n] = ct++;
          yushu[Mp[wavy[i] % n]][1][wavy[i] / 1000000]++;
        } else {
          if (Mp[wavy[i] % n] == 0) Mp[wavy[i] % n] = ct++;
          yushu[Mp[wavy[i] % n]][0][wavy[i] / 1000000]++;
        }
      }
    }
    long long t = 0;
    long long tmp = 0;
    while (cnt + tmp < k && t < nwavy) {
      cnt += tmp;
      tmp = 0;
      if (wavy[t] < 10) {
        for (int j = 0; j < 10; j++) {
          if (j < wavy[t])
            tmp += yushu[Mp[(n - wavy[t] % n * 10000000 % n) % n]][0][j];
          else if (j > wavy[t])
            tmp += yushu[Mp[(n - wavy[t] % n * 10000000 % n) % n]][1][j];
        }
      } else {
        if (wavy[t] % 10 > (wavy[t] / 10) % 10) {
          for (int j = 0; j < wavy[t] % 10; j++)
            tmp += yushu[Mp[(n - wavy[t] % n * 10000000 % n) % n]][0][j];
        } else {
          for (int j = wavy[t] % 10 + 1; j < 10; j++)
            tmp += yushu[Mp[(n - wavy[t] % n * 10000000 % n) % n]][1][j];
        }
      }
      t++;
    }
    if (cnt + tmp < k) {
      printf("-1\n");
    } else if (t == nwavy && cnt + tmp == k) {
      printf("98989898989898\n");
    } else {
      long long m = wavy[t - 1] * 10000000;
      for (int i = 22659; cnt < k; i++) {
        if ((m + wavy[i]) % n == 0 && check(m + wavy[i])) {
          cnt++;
          if (cnt == k) {
            printf("%I64d\n", m + wavy[i]);
            break;
          }
        }
      }
    }
  }
  return 0;
}