eolymp
bolt
Try our new interface for solving problems
Problems

Digits

Digits

Time limit 1 second
Memory limit 64 MiB

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 findn positive integers with equal sum of digits and minimal possible total sum. Dima has other importantthings to do, so he asked you to write a program that solves this problem for him.

Input data

Contains a single integer n (1n5000).

Output data

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

Examples

Input example #1
2
Output example #1
11
Input example #2
3
Output example #2
33
Source 2014 ACM NEERC, Northern Subregion, November 8, Problem D