Description

Little Petya likes integers. Recently he has learned about different properties of sums of number's digits. For example, if the sum of number's digits is divisible by $9$ , then the number itself is divisible by $9$ as well.

Now little Petya is interested in numbers with equal sum of digits. He asks his older brother Dima to find $n$ positive integers with equal sum of digits and minimal possible total sum. Dima has other important things to do, so he asked you to write a program that solves this problem for him.

Input Format

Input file contains a single integer $n (1 \le n \le 5000)$ .

Output Format

Output the minimal possible sum of $n$ positive integers, that all have same sum of digits.

2

11

3

33

Hint

Time limit: 2 s, Memory limit: 256 MB.