Smallest Integer with K Distinct Digits

Time limit2sMemory limit128 MB

Summary

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.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Backtracking, Math
Solved: No attempts yet

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.

Examples4

Example 1
Input
```
47 1
```
Expected output
```
55
```
Example 2
Input
```
12364 3
```
Expected output
```
12411
```
Example 3
Input
```
7 3
```
Expected output
```
102
```
Example 4
Input
```
69 2
```
Expected output
```
69
```