Фрэнк Таранти — главный специалист по оружию в бригаде Вито Маретти. Он занимается тем, что покупает краденое оружие и перебивает на нем серийные номера. После этого оружие поступает в распоряжение членов бригады.

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

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

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