Problem Description

Given four positive integers $K,~S,~P,~D$, in decimal, find the smallest $K$-digit natural number $x$ such that the sum of digits of $x$ is $S$, and the sum of digits of $x \times D$ is $P$.

Input Format

The input contains one line with four integers: $K,~S,~P,~D$.

Output Format

Output one integer in one line, representing the smallest natural number $x$ that satisfies the conditions. If it does not exist, output $-1$.

2 9 9 5

18

Hint

Constraints: $1~\leq~K~\leq~100,~1~\leq~S,~P~\leq~1000,~1~\leq~D~\leq~9$.

Translated by ChatGPT 5