ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

## G. Next Number

Time limit: 1.0 second
Memory limit: 64 MB
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

inputoutput
```113
```
```122
```
```0050
```
```0104
```
Problem Author: Alexander Ipatov
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)
To submit the solution for this problem go to the Problem set: 1406. Next Number