2022는 무엇이 특별할까?

• N을 d진법으로 바꾼 뒤에, 조건을 만족하는 d자리 숫자를 찾는것은 백트래킹을 잘 써서 구하는 것이 효율적이긴 하다.
• 하지만 쉽게 구현하려면, 그냥 (0, …, d-1) 의 모든 퍼뮤테이션을 N보다 큰 수가 나올때까지 이터레이션 시키는 것으로도 충분하다. d!개의 퍼뮤테이션에 대해서, 크기비교에 O(d)가 걸리므로 O(d*d!) 인데, d⇐9 이므로 충분히 동작한다.
• N을 d진법으로 바꿨을때 길이가 d보다 작으면 최솟값을, d보다 크면 -1을 출력해야 하는 처리를 빼먹지 말자. 최솟값은 d=5 을 예로 들면 10234(d) 이다.

"""Solution code for "BOJ 24268. 2022는 무엇이 특별할까?".

- Problem link: https://www.acmicpc.net/problem/24268
- Solution link: http://www.teferi.net/ps/problems/boj/24268

Tags: [Brute Force]
"""

import itertools


def main():
    N, d = [int(x) for x in input().split()]

    min_num = int(''.join(str(x) for x in (1, 0, *range(2, d))), d)
    if N < min_num:
        print(min_num)
        return
    max_num = int(''.join(str(x) for x in reversed(range(d))), d)
    if N >= max_num:
        print('-1')
        return

    base_d = []
    while N > 0:
        N, r = divmod(N, d)
        base_d.append(r)
    base_d = tuple(reversed(base_d))

    
    num = next(x for x in itertools.permutations(range(d)) if x > base_d)
    print(int(''.join(str(x) for x in num), d))


if __name__ == '__main__':
    main()