Задача D. Счастливый билетик

Автор:Владимир Ульянцев, Сергей Поромов   Ограничение времени:2 сек
Входной файл:lucky.in   Ограничение памяти:256 Мб
Выходной файл:lucky.out  

Условие

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

Билетик называется счастливым, если сумма цифр на четных позициях в его номере равна сумме цифр на нечетных позициях.

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

Формат входного файла

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

Формат выходного файла

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

Примеры тестов

Входной файл (lucky.in) Выходной файл (lucky.out)
1
123123
123134
2
99
110

0.071s 0.011s 13