자릿수 이론

한 학생이 자연수를 한 자리 수로 곱하거나 나눌 때 자릿수의 합이 어떻게 변하는지 조사하게 되었다. 어느 날 그는 자연수 A의 자릿수의 합과 D×A의 자릿수의 합을 알 때 A를 복원할 수 있는지 궁금해졌다. 여기서 D는 주어진 한 자리 수이다. 얼마 지나지 않아 이 정보만으로는 A를 복원하기에 충분하지 않다는 것을 알아냈다. 예를 들어 9와 45는 자릿수의 합이 같다. 이들을 5로 곱하면 45와 225가 되는데, 이들 역시 자릿수의 합이 같다.

그래서 그는 A의 십진수 자릿수 개수 K를 알고 있다는 조건에서 이 질문에 대한 답을 찾기 시작했다. 아쉽게도 여기서도 실망스러운 결과가 나왔다. 자릿수 개수와 자릿수의 합이 같은 어떤 수들은 같은 수를 곱한 뒤에도 그 합이 다시 같아진다. 예를 들어 D = 3일 때 42와 51이 그러하다.

그래서 그는 다음과 같은 문제를 세웠다. 십진법에서 자릿수의 합이 S이고 D×A의 자릿수의 합이 P인 가장 작은 K자리 자연수 A를 찾는 것이다.

이 문제를 해결하는 프로그램을 작성해야 한다.

입력 파일에는 네 개의 자연수 K, S, P, D가 주어진다. (1 ≤ K ≤ 100, 1 ≤ S ≤ 9K, 1 ≤ P ≤ 9(K+1), 1 ≤ D ≤ 9)

A가 존재하면 A를, 존재하지 않으면 -1을 출력한다. A는 0으로 시작할 수 없다.