Find a Number

3000ms

262144K

Description:

You are given two positive integers $$$d$$$ and $$$s$$$. Find minimal positive integer $$$n$$$ which is divisible by $$$d$$$ and has sum of digits equal to $$$s$$$.

Input:

The first line contains two positive integers $$$d$$$ and $$$s$$$ ($$$1 \le d \le 500, 1 \le s \le 5000$$$) separated by space.

Output:

Print the required number or -1 if it doesn't exist.

Sample Input:

13 50

Sample Output:

Sample Input:

61 2

Sample Output:

1000000000000000000000000000001

Sample Input:

15 50

Sample Output:

-1

Informação

Provedor Codeforces

Código CF1070A