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

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

Вхідні дані

Містить одне ціле число n (1 ≤ n ≤ 5000).

Вихідні дані

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