Задачка 5 Теорияцифр Имя входного файла:digit.in Имя выходного файла: digit.out

Задачка 5 Теория
цифр





Имя входного файла:


digit.in





Имя выходного файла:


digit.out





Наибольшее время работы на одном тесте:


1 секунда





Максимальный объем используемой памяти:


256 мб

Молодой информатик стал изучить, как меняются суммы цифр
естественных чисел при умножении и разделении на различные однозначные числа. Единожды
он задался вопросом, можно ли вернуть число A, если нам
знаменита сумма его цифр, а также сумма цифр числа DA, где D данное однозначное
число. Достаточно скоро он установил, что для возрождения числа А этой информации недостаточно. Так,
к примеру, у чисел 9 и 45 однообразные суммы цифр. Если же их помножить на 5, то
получим числа 45 и 225, которые тоже имеют схожие суммы цифр.

Тогда молодой информатик стал отыскивать ответ на поставленный
вопрос при условии, что нам знаменито K
количество десятичных символов в числе A. К раскаянью, и здесь его
ждало разочарование. У неких чисел, имеющих однообразное количество цифр и однообразные
суммы цифр, после умножения на один и тот же множитель эти суммы вновь оказываются
одинаковыми. Такими числами, например, являются 42 и 51 при D = 3.

И тогда молодой информатик поставил перед собой такую задачу:
отыскать меньшее Kзначное естественное число A в десятичной системе счисления, которое имеет сумму цифр,
одинаковую S, а число DA имеет
сумму цифр, одинаковую P.

Нужно написать программку, решающую поставленную задачку.

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

Во входном файле заданы четыре натуральных числа K, S, P, D (1 K 100, 1 S 9K, 1 P 9(K+1), 1 D 9).

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

Выведите в выходной файл число A, если оно
существует, либо 1, в неприятном случае. Число A не может
начинаться с нуля.

Образцы




digit.in


digit.out




2 9 9 5


18




2 8 10 3


-1