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

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

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

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

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

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

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

Пример:

Вход

13

Ответ

12

123456789101112 => 1234567891012