ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1406. Следующее число

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Фрэнк Таранти — главный специалист по оружию в бригаде Вито Маретти. Он занимается тем, что покупает краденое оружие и перебивает на нем серийные номера. После этого оружие поступает в распоряжение членов бригады.
Недавно Вито поручил Фрэнку срочно достать 20 новых автоматов. Фрэнк выполнил задание той же ночью. И теперь ему предстоит исправить номера. Для того чтобы оружие не было слишком подозрительным, он использует в качестве нового номера наименьшее из следующих по порядку чисел с такой же суммой цифр как в исходном номере. Поиск такого числа обычно отнимает у Фрэнка полчаса — он ведь гангстер, а не математик. Но в этот раз он не может потратить и пару минут на то, чтобы найти новые номера, он угрожает Вам одним из новых автоматов с целью заставить написать программу, которая поможет ему с этой задачей.

Исходные данные

В единственной строке записано K-значное число N — старый номер автомата (1 ≤ K ≤ 2000; 0 ≤ N ≤ 101000).

Результат

Выведите нужный Фрэнку новый K-значный номер или число -1, если такого номера не существует.

Примеры

исходные данныерезультат
113
122
0050
0104
Автор задачи: Александр Ипатов
Источник задачи: XII командный чемпионат школьников Свердловской области по программированию (15 октября 2005 года)