Маленький Петя любит целые числа. Недавно он изучил различные свойства сумм цифр числа. Например, если сумма цифр числа делится на 9, то и само число делится на 9.

Сейчас маленького Петю интересуют числа с одинаковой суммой цифр. Он просит старшего брата Диму найти n натуральных чисел с одинаковой суммой цифр и наименьшей возможной общей суммой. У Димы есть другие дела, поэтому он попросил Вас написать программу, решающую эту задачу.

Входные данные

Содержит одно целое число n (1 ≤ n ≤ 5000).

Выходные данные

Вывести наименьшую возможную сумму n натуральных чисел, сумма цифр которых одинакова.