[JSOI2013] 数字理论

题目描述

给定 $4$ 个正整数 $K,~S,~P,~D$，要求在十进制数中，寻找一个最小的 $K$ 位自然数 $x$，满足 $x$ 的各个数位之和为 $S$，并且 $x$ 乘以 $D$ 之后各个数位之和为 $P$。

输入格式

输入数据中包含一行四个整数，分别为 $K,~S,~P,~D$。

输出格式

输出一行一个整数，表示满足条件的最小自然数 $x$。如果不存在则输出$-1$。

样例 #1

样例输入 #1

2 9 9 5

样例输出 #1

18

提示

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