Originally Posted by
blisskinny
Frank Tarantini is the main weapons specialist in the gang of Vito Maretti. He buys stolen weapons and forges the gun numbers. After that the weapons is given to the other gangsters.
Recently Vito has charged Frank with the assignment to procure 20 new tommy-guns. Frank has fulfilled the assignment the same night. Now he is to change the guns numbers. In order not to arouse suspicion Frank uses as a new gun number the minimal next one with the same sum of digits. It takes 30 minutes to find such number because Frank is a gangster, not mathematician. But today he is short of time. So you are under the threat of one of his new tommy-guns. He wants you to write a program that would find the suitable number.
Input
consists of the k-digit number N – the old number of a tommy-gun (1 <= K <= 2000, 0 <= N <= 101000).
Output
the new K-digit number that Frank needs or -1 if there is no such number.
Samples
input
113
0050
output
122
0104
