Smallest Positive Integer with Given Digit Sum

Given a positive integer S, find the smallest positive integer whose digits sum exactly to S. The sum of the digits of an integer N is defined as \(S = \sum_{i=1}^{n} d_i\), where \(d_1, d_2, \ldots, d_n\) are the digits of N. If S is less than or equal to 9, the answer is simply S. For larger values, the number is constructed by repeatedly subtracting 9 from S and then positioning the remaining digit at the beginning of the result.

For example, when S = 10, the answer is 19.

inputFormat

The input consists of a single integer S (1 ≤ S ≤ 10⁹), provided via standard input (stdin).

outputFormat

Output the smallest positive integer whose digits sum to S using standard output (stdout).

10

19