Finding an integer

Find the smallest integer at least N whose decimal digits contain d1 at least c1 times and d2 at least c2 times.

Hard8GreedyImplementationBrute forceMathInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

Consider the natural numbers greater than or equal to $N$ whose decimal representation contains the digit $d_1$ at least $c_1$ times and the digit $d_2$ at least $c_2$ times.

Write a program that finds the smallest such number.

Input

The first line contains $N$ , $d_1$ , $c_1$ , $d_2$ , $c_2$ , separated by spaces. ( $1 \le N < 10^{15}$ , $0 \le d_1, d_2 \le 9$ , $d_1 \ne d_2$ , $0 \le c_1$ , $0 \le c_2$ , $c_1 + c_2 \le 15$ )

Output

Print the smallest number that satisfies the condition on the first line. The answer fits in a 64-bit integer.