Smallest Integer with K Distinct Digits

Given N up to 10^18 and K up to 10, construct the smallest integer at least N that contains exactly K distinct decimal digits.

Medium7Dynamic programmingGreedyBacktrackingMathNo attempts yetTime limit2sMemory limit128 MB

Description

Examples4

Problem

You are given natural numbers N and K. Among all natural numbers greater than or equal to N, find the smallest number that uses exactly K distinct decimal digits.

Input

The first line contains N and K separated by a space.

N is a natural number not greater than 10^18. K is a natural number not greater than 10.

Output

Output the smallest natural number that satisfies the condition.