Smallest Integer with Given Digit Sum

You are given a non-negative integer \(N\). Your task is to find the smallest non-negative integer \(M\) such that the sum of its digits is equal to \(N\).

Formally, let \(M\) be represented by digits \(d_1d_2\dots d_k\) (without leading zeros) such that \(d_1 + d_2 + \cdots + d_k = N\). You need to find the minimum possible \(M\) satisfying this condition.

For example, for \(N = 15\), the smallest integer with digits summing to 15 is 69 because \(6 + 9 = 15\) and there is no smaller number with this property.

inputFormat

The input consists of a single non-negative integer \(N\) read from standard input (stdin), where \(0 \leq N \leq 1000\) (assumed).

outputFormat

Output the smallest non-negative integer \(M\) such that the sum of its digits is equal to \(N\). The output should be written to standard output (stdout).

15

69