题目描述

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 file contains a single integer $n (1 \le n \le 5000)$ .

输出格式

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

题目大意

输入一个整数n，要求找到n个不同的正整数，使得这n个正整数数位和一样且总和最小，输出这个总和
数位和：一个数每一位的值的和，比如123的数位和为1+2+3=6

样例一解释：选择了1和10两个数
样例二解释：选择了2，11和20这三个数

2

11

3

33

提示

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