Problem Statement

There is nothing more beautiful than just an integer number.

You are given an integer n. Write down n in decimal notation with no leading zeroes, and let M be the number of written digits. Perform the following operation exactly k times:

• Choose two different 1-based positions, i and j, such that 1 <= i < j <= M. Swap the digits at positions i and j. This swap must not cause the resulting number to have a leading zero, i.e., if the digit at position j is zero, then i must be strictly greater than 1.

Return the maximal possible number you can get at the end of this procedure. If it's not possible to perform k operations, return -1 instead.

Definition

 Class: TheSwap Method: findMax Parameters: int, int Returns: int Method signature: int findMax(int n, int k) (be sure your method is public)

Constraints

-n will be between 1 and 1,000,000, inclusive.
-k will be between 1 and 10, inclusive.

Examples

0)

 16375 1
Returns: 76315
 The optimal way is to swap 1 and 7.
1)

 432 1
Returns: 423
 In this case the result is less than the given number.
2)

 90 4
Returns: -1
 We can't make even a single operation because it would cause the resulting number to have a leading zero.
3)

 5 2
Returns: -1
 Here we can't choose two different positions for an operation.
4)

 436659 2
Returns: 966354

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10369

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13699&pm=10369

Vasyl[alphacom]

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Recursion, Simple Search, Iteration