Здравствуйте. Как решить эту задачу ?

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

Формат входных данных

В единственной строке задан номер билетика Васи — натуральное число, имеющее в своей десятичной записи не более 100 цифр.

Формат результата

Выведите минимальный номер счастливого билетика, который больше номера билетика Васи.