E. Wavy numbers

#define _CRT_SECURE_NO_DEPRECATE
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>

using namespace std;

#pragma comment(linker, "/STACK:128000000")

typedef pair<int, int> pii;
typedef long long int64;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;

int64 n, k;
vvpii upstream, downstream;
vpii totalup, totaldown;
vi allnumbers;
vi digits;

void generate_upstream(int pos, int value, vpii &a)
{
    allnumbers.push_back(value);

    if (pos == 7)
    {
        a.push_back(pii((int)(value % n), value));
        digits.pop_back();
        return;
    }

    if (pos & 1)
    {
        for (int i = digits.back() + 1; i < 10; ++i)
        {
            digits.push_back(i);
            generate_upstream(pos + 1, value * 10 + i, a);
        }
    } else {
        for (int i = 0; i < digits.back(); ++i)
        {
            digits.push_back(i);
            generate_upstream(pos + 1, value * 10 + i, a);
        }
    }

    digits.pop_back();
}

void generate_downstream(int pos, int value, vpii &a)
{
    allnumbers.push_back(value);

    if (pos == 6)
    {
        upstream[0].push_back(pii((int)(value % n), value));
    }

    if (pos == 7)
    {
        a.push_back(pii((int)(value % n), value));
        digits.pop_back();
        return;
    }

    if (!(pos & 1))
    {
        for (int i = digits.back() + 1; i < 10; ++i)
        {
            digits.push_back(i);
            generate_downstream(pos + 1, value * 10 + i, a);
        }
    } else {
        for (int i = 0; i < digits.back(); ++i)
        {
            digits.push_back(i);
            generate_downstream(pos + 1, value * 10 + i, a);
        }
    }

    digits.pop_back();
}

inline int get_total_leftmost(vpii &a, int md, int ind)
{
    pii cur(md, (ind << 26));
    int res = (int)a.size();
    int l = 0, r = res - 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] >= cur)
        {
            res = mid;
            r = mid - 1;
            continue;
        }
        else
            l = mid + 1;
    }
    if (res == (int)a.size()) return 0;
    if (a[res].first != md) return 0;
    return (a[res].second & 67108863);
}

inline int get_total_rightmost(vpii &a, int md, int ind)
{
    pii cur(md, (ind << 26) | 67108863);
    int res = -1;
    int l = 0, r = (int)a.size() - 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] <= cur)
        {
            res = mid;
            l = mid + 1;
            continue;
        }
        else
            r = mid - 1;
    }
    if (res == -1) return 0;
    if (a[res].first != md) return 0;
    return (a[res].second & 67108863);
}

inline int get_leftmost(vpii &a, int md)
{
    int res = -1;
    int l = 0, r = (int)a.size() - 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (a[mid].first == md)
        {
            res = mid;
            r = mid - 1;
            continue;
        }
        if (a[mid].first > md)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return res;
}

inline int get_rightmost(vpii &a, int md)
{
    int res = -1;
    int l = 0, r = (int)a.size() - 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (a[mid].first == md)
        {
            res = mid;
            l = mid + 1;
            continue;
        }
        if (a[mid].first > md)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return res;
}

inline int get_count(vpii &a, int md)
{
    int left_ind = get_leftmost(a, md);
    if (left_ind == -1) return 0;
    int right_ind = get_rightmost(a, md);
    return right_ind - left_ind + 1;
}

inline int get_kth(vpii &a, int md, int kvalue)
{
    int left_ind = get_leftmost(a, md);
    return left_ind + kvalue - 1;
}

int main()
{
    cin >> n >> k;

    upstream.resize(10);
    downstream.resize(10);
    for (int i = 1; i < 10; ++i)
    {
        digits.push_back(i);
        generate_upstream(1, i, upstream[i]);

        digits.push_back(i);
        generate_downstream(1, i, downstream[i]);

        sort(upstream[i].begin(), upstream[i].end());
        sort(downstream[i].begin(), downstream[i].end());
    }
    sort(upstream[0].begin(), upstream[0].end());

    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < (int)upstream[i].size(); ++j)
            totalup.push_back(pii(upstream[i][j].first, (i << 26)));
        for (int j = 0; j < (int)downstream[i].size(); ++j)
            totaldown.push_back(pii(downstream[i][j].first, (i << 26)));
    }

    sort(totalup.begin(), totalup.end());
    sort(totaldown.begin(), totaldown.end());

    for (int i = 0; i < (int)totalup.size(); ++i)
    {
        ++totalup[i].second;
        if (i && totalup[i].first == totalup[i - 1].first)
            totalup[i].second += (totalup[i - 1].second & 67108863);
    }

    for (int i = (int)totaldown.size() - 1; i >= 0; --i)
    {
        ++totaldown[i].second;
        if (i + 1 != (int)totaldown.size() && totaldown[i + 1].first == totaldown[i].first)
            totaldown[i].second += (totaldown[i + 1].second & 67108863);
    }

    sort(allnumbers.begin(), allnumbers.end());

    for (int i = 0; i < (int)allnumbers.size(); ++i)
    {
        if (i && allnumbers[i] == allnumbers[i - 1]) continue;
        if (allnumbers[i] % n) continue;
        --k;
        if (!k)
        {
            cout << allnumbers[i] << endl;
            return 0;
        }
    }

    for (int i = 0; i < (int)allnumbers.size(); ++i)
    {
        if (i && allnumbers[i] == allnumbers[i - 1]) continue;
        int value = allnumbers[i];
        int64 md64 = (n - ((int64)value * 10000000LL) % n) % n;
        if (md64 >= 10000000LL) continue;
        int md = (int)md64;
        if (value < 10)
        {
            for (int i = 0; i < value; ++i)
            {
                int cnt = get_count(upstream[i], md);
                if (cnt < k)
                {
                    k -= cnt;
                    continue;
                }
                int ind = get_kth(upstream[i], md, (int)k);
                int64 res = (int64)value * 10000000LL + (int64)upstream[i][ind].second;
                cout << res << endl;
                return 0;
            }
            for (int i = value + 1; i < 10; ++i)
            {
                int cnt = get_count(downstream[i], md);
                if (cnt < k)
                {
                    k -= cnt;
                    continue;
                }
                int ind = get_kth(downstream[i], md, (int)k);
                int64 res = (int64)value * 10000000LL + (int64)downstream[i][ind].second;
                cout << res << endl;
                return 0;
            }
            continue;
        }
        int last_digit = value % 10;
        int prelast_digit = (value / 10) % 10;
        if (prelast_digit < last_digit)
        {
            int cnt = get_total_rightmost(totalup, md, last_digit - 1);

            if (cnt < k)
            {
                k -= cnt;
                continue;
            }

            for (int i = 0; i < last_digit; ++i)
            {
                int cnt = get_count(upstream[i], md);
                if (cnt < k)
                {
                    k -= cnt;
                    continue;
                }
                int ind = get_kth(upstream[i], md, (int)k);
                int64 res = (int64)value * 10000000LL + (int64)upstream[i][ind].second;
                cout << res << endl;
                return 0;
            }
        } else {
            int cnt = get_total_leftmost(totaldown, md, last_digit + 1);

            if (cnt < k)
            {
                k -= cnt;
                continue;
            }

            for (int i = last_digit + 1; i < 10; ++i)
            {
                int cnt = get_count(downstream[i], md);
                if (cnt < k)
                {
                    k -= cnt;
                    continue;
                }
                int ind = get_kth(downstream[i], md, (int)k);
                int64 res = (int64)value * 10000000LL + (int64)downstream[i][ind].second;
                cout << res << endl;
                return 0;
            }
        }
    }

    cout << -1 << endl;

    return 0;
}