Winning Lottery

Harshit knows by his resources that this time the winning lottery number is the smallest number whose sum of the digits is S and the number of digits is D. You have to help Harshit and print the winning lottery number.

Input Format

The Input line contains two space-separated integers: S,D

Output Format

The output contains a single integer denoting the winning lottery number

Constraints

1 <= D <= 1000
1 <= S <= 9*D
Time Limit: 1 second

Sample Input1:

9 2

Sample Output1:

18

Explanation

There are many other possible numbers like 45, 54, 90, etc with the sum of digits as 9 and number of digits as 2. The smallest of them is 18.

class Main {
    public static String findSmallest(int sum, int digits) {
        // We want the smallest number, so we can just
        // start giving biggest digits possible to last positions(LSP)
        char[] str = new char[digits];
        for (int i = digits - 1; i >= 0; i--) {
            int digit = 9;
            // Reserving 1 for the first digit
            if (digit + 1 > sum)
                if (i == 0)
                    digit = sum;
                else
                    digit = sum - 1;
            str[i] = (char) (digit + '0');
            sum -= digit;
        }
        return new String(str);
    }
}