Smallest Number With Digit Sum

You are given two integers digitSum and numDigits.

Construct the smallest number that has exactly numDigits digits, with no leading zeros, so the first digit must be at least 1, and whose digits add up to exactly digitSum.

Return the number as a string, since it can be far too large for any integer type. If no such number exists, return the string "-1". In particular, digitSum = 0 has no valid answer, because the first digit must be at least 1, and digitSum > 9 * numDigits is impossible.

Examples

Example 1

Input: digitSum = 5, numDigits = 3
Output: "104"
Explanation: 104 has three digits summing to 1 + 0 + 4 = 5. No smaller 3-digit number works: 100 through 103 have digit sums 1 through 4.

Example 2

Input: digitSum = 20, numDigits = 3
Output: "299"
Explanation: Putting the largest digits at the end minimizes the number: 2 + 9 + 9 = 20.

Example 3

Input: digitSum = 28, numDigits = 3
Output: "-1"
Explanation: Three digits sum to at most 27.