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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor