Задача “ЕГЭ”

Семен готовился к ЕГЭ по информатике и встретил в демо-версии ЕГЭ 2017 года такую задачу:

«Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

  1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
  2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходное число: 3165. Суммы: 3+1 = 4; 6+5 = 11. Результат: 114.

Укажите наименьшее число, в результате обработки которого автомат выдаст число 1311.»

 

Семен решил, что для самопроверки он напишет программу, которая решает подобную задачу. Мы думаем, что вы тоже с этим справитесь.

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

Программа получает на вход некоторое натуральное число N, которое может содержать две, три или четыре цифры.

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

Программа должна вывести такое наименьшее целое четырёхзначное число K, после применения к которому описанного выше алгоритма получается число N. Если же такого числа не существует, программа должна вывести число 0.

Пример

Входные данные Выходные данные
1311 2949