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;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
unordered_map<int, int> M[10][2];
vector<pair<int, int>> was;
int bs[20], T;
void cal(int num) {
  int cnt = 0, tmp = num;
  while (tmp > 0) {
    bs[++cnt] = (tmp % 10);
    tmp /= 10;
  }
  for (int i = 2; i <= cnt - 1; i++) {
    bool ok = (bs[i] < bs[i - 1] && bs[i] < bs[i + 1]) ||
              (bs[i] > bs[i - 1] && bs[i] > bs[i + 1]);
    if (!ok) return;
  }
  was.push_back({num, num % ln});
  if (num % ln == 0) T++;
  if (cnt == 7) {
    M[bs[7]][bs[7] < bs[6]][num % ln]++;
  } else if (cnt == 6 && bs[5] < bs[6]) {
    M[0][1][num % ln]++;
  }
}
void pp(int x, int y, long long cur) {
  for (auto p : was) {
    int num = p.first, md = p.second;
    if (md != y) continue;
    int cnt = 0, tmp = num;
    while (tmp > 0) {
      bs[++cnt] = (tmp % 10);
      tmp /= 10;
    }
    if (cnt < 6 || (cnt == 6 && bs[6] < bs[5])) continue;
    if (cnt == 6) bs[7] = 0;
    if (x < 10) {
      if (bs[7] < x && bs[7] < bs[6])
        cur++;
      else if (bs[7] > x && bs[7] > bs[6])
        cur++;
    } else {
      int a = x % 10, b = (x / 10) % 10;
      if (b < a) {
        if (bs[7] < a && bs[7] < bs[6]) cur++;
      } else {
        if (bs[7] > a && bs[7] > bs[6]) cur++;
      }
    }
    if (cur == lk) {
      printf("%d", x);
      if (cnt == 6)
        printf("0%d\n", num);
      else
        printf("%d\n", num);
      return;
    }
  }
}
bool ck(long long tmp) {
  int cnt = 0;
  while (tmp > 0) {
    bs[++cnt] = (tmp % 10);
    tmp /= 10;
  }
  for (int i = 2; i <= cnt - 1; i++) {
    bool ok = (bs[i] < bs[i - 1] && bs[i] < bs[i + 1]) ||
              (bs[i] > bs[i - 1] && bs[i] > bs[i + 1]);
    if (!ok) return 0;
  }
  return 1;
}
int gg[200];
void test() {
  long long pp = ln;
  for (int(i) = 1; (i) <= (int)(lk); (i)++) {
    while (!ck(pp)) pp += ln;
    cout << pp << endl;
    pp += ln;
  }
}
int main() {
  scanf("%lld%lld", &ln, &lk);
  for (int(i) = 1; (i) <= (int)(9999999); (i)++) {
    if (i < 100 && i % 11 == 0) continue;
    cal(i);
    if (T == lk) {
      printf("%d\n", i);
      return 0;
    }
  }
  int i = 0;
  long long cur = T;
  for (; i < was.size(); i++) {
    int num = was[i].first, md = was[i].second;
    long long round = 0;
    long long x = (ln - (long long)md * 10000000 % ln) % ln;
    if (x > 10000000) continue;
    int y = (int)x;
    if (num < 10) {
      for (int(j) = 0; (j) < (int)(10); (j)++)
        if (num < j) {
          if (M[j][0].find(y) != M[j][0].end()) round += M[j][0][y];
        } else if (j < num) {
          if (M[j][1].find(y) != M[j][1].end()) round += M[j][1][y];
        }
    } else {
      int a = num % 10, b = (num / 10) % 10;
      if (a == b) continue;
      if (b < a) {
        for (int(j) = 0; (j) < (int)(a); (j)++) {
          if (M[j][1].find(y) != M[j][1].end()) round += M[j][1][y];
        }
      } else {
        for (int j = a + 1; j < 10; j++) {
          if (M[j][0].find(y) != M[j][0].end()) round += M[j][0][y];
        }
      }
    }
    if (cur + round >= lk) {
      pp(num, y, cur);
      return 0;
    }
    cur += round;
  }
  puts("-1");
  return 0;
}