Республиканская олимпиада по информатике 2010 года за 11 класс | Казахстанские олимпиады

Задача E. Цифры

Ержан выписал все числа от $1$ до $X$ в ряд без пробелов. Затем, из каждой группы последовательных одинаковых цифр он оставил ровно одну цифру. В итоге осталось написано $S$ цифр, но Ержан забыл, до какого $X$ он выписывал числа вначале. Помогите ему — найдите $X$.

Формат входного файла

Входной файл содержит одно целое число $S$ ($1 \le S \le 10^{18}$).

Формат выходного файла

Выходной файл должен содержать одно целое число $X$. Если нужного числа не существует выведите $-1$.

Примеры

Вход

13

Выход

12