Digit Rearrangement

Interview

Time limit2sMemory limit512 MB

Summary
Given A and B, rearrange the digits of A (no leading zero) to build the largest permutation that is still strictly less than B, or print -1.
Level

Medium6 of 10

Topics
Backtracking, Greedy, Sorting, String matching
Solved
No attempts yet

Problem

Given two integers A and B, you want to rearrange the digits contained in A to form a new number C. That is, C must be one of the permutations of A.

Among all possible C, find the largest value that is less than B. C must not start with 0.

Input

The first line contains two integers A and B.

Output

Print the largest C that is less than B. If no such C exists, print -1.

Constraints

  • 1 ≤ A, B < 10^9

Examples3

  1. Example 1

    Input
    1234 3456
    Expected output
    3421

  2. Example 2

    Input
    1000 5
    Expected output
    -1

  3. Example 3

    Input
    789 123
    Expected output
    -1