Largest Number Less Than N Using Allowed Digits

Given a positive integer N and an array of digits A, where every element in A is between 0 and 9. Each allowed digit may be used an unlimited number of times. Construct the largest non-negative integer that is strictly smaller than N and whose decimal representation consists only of digits from A. Rules: The result cannot have leading zeros, except for the number 0 itself. If no valid number can be constructed, output -1. N can be very large and should be handled as a decimal string. Input Format First line: a positive integer N. Second line: digits in A, separated by spaces. Output Format Print the largest constructible integer strictly smaller than N, or -1 if none exists. Example Input 23415 2 4 9 Output 22999 Explanation: 22999 < 23415, and no larger number made solely from {2, 4, 9} satisfies the condition. Constraints 1 <= len(N) <= 100000 N has no leading zeros. 1 <= len(A) <= 10 A[i] is an integer from 0 to 9. Example Input 23415 2 4 9 Output 22999