Building a Large Number

Interview

Time limit1sMemory limit256 MB

Summary
Given N and a digit set K (size 1 to 3), find the largest number at most N whose digits all come from K.
Level

Medium5 of 10

Topics
Greedy, Backtracking, Implementation, Brute force
Solved
No attempts yet

Problem

Write a program that prints the largest natural number less than or equal to N whose digits all belong to the set K. Every element of K is a natural number from 1 to 9.

For example, when N=657 and K={1, 5, 7}, the answer is 577.

Input

The first line gives N and the number of elements of K, separated by a space, as natural numbers. (10 ≤ N ≤ 100,000,000, 1 ≤ number of elements of K ≤ 3) The second line gives the elements of K, separated by spaces. Each element is a natural number from 1 to 9.

The input is always given so that a natural number less than or equal to N made only of elements of K can be formed.

Output

On the first line, print the largest natural number less than or equal to N whose digits all belong to K.

Examples1

  1. Example 1

    Input
    657 3
1 5 7
    Expected output
    577