Задача E. Простая сумма

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Найдите наименьшее натуральное число, сумма цифр которого равна n.

Формат входных данных

Единственная строка входного файла содержит натуральное число n.

Формат выходных данных

Выведите одно натуральное число — ответ на задачу.

Ограничения

1 ≤ n ≤ 105

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 20, получат не менее 20 баллов.

Примеры тестов

Стандартный вход Стандартный выход
1
18
99

0.070s 0.016s 15