Smallest Number with Given Digit Sum

Given a non-negative integer N, your task is to find the smallest positive integer X such that the sum of its digits is exactly N. In other words, if the digits of X are denoted as d₁, d₂, ..., d_k, then they must satisfy the equation:

\(d_1 + d_2 + \cdots + d_k = N\)

If N is 0, the answer is defined to be 0. The goal is to construct the smallest possible number X meeting the criteria.

Example:

• For N = 10, the smallest number is 19 because \(1 + 9 = 10\) and no smaller number satisfies this condition.
• For N = 15, the smallest number is 69 since \(6 + 9 = 15\).

The problem can be approached using a greedy strategy by repeatedly subtracting 9 from N and arranging the remaining digits in increasing order.

inputFormat

The input consists of a single integer N (0 ≤ N ≤ 10⁹) provided via standard input. It represents the target sum of the digits.

Input is read from stdin.

outputFormat

Output the smallest number X (without leading zeros) whose digits sum up to N using standard output (stdout).

## sample

10

19