SOLVE
LATER
Little Santa made a list of all the naughty children. He created a programming problem and he will give gift to only those naughty children who will solve that problem. The problem is:
Given three integers, $$n, k, x$$ (without leading zeros), you can insert at most $$k$$ digits at any positions in $$n$$. You have to create the maximum number (without leading zeros) from $$n$$ which is not greater than $$x$$.
All the children want gifts so they asked you to solve the problem for them.
Input format:
First line of input contains three integers, $$n, k, x$$ $$(1 <= n <= x <= 10^{100000})$$, $$(0 <= k <= 100000)$$.
Output format:
Print one integer, denoting the maximum number (without leading zeros) that can be created from $$n$$ which is not greater than $$x$$ after inserting at most $$k$$ digits at any position in $$n$$.
You have to insert at most 2 digits in number 10 to make it no larger than 109. Inserting 9 at the end is the way to get the best result. There are also other valid strategies, like not inserting digits at all or inserting 0 at second position, but they give smaller numbers.