Задача K. Мёртвая вода ≡

Условие

На полке у Кащея стоят бутылки с водой объёмом от 1 до n. Иван-царевич знает, что мёртвая вода только в тех ёмкостях, сумма цифр объёма которых равна 13. Кащей разрешил герою взять только одну бутылку. Какой наибольший объём мёртвой воды может получить Иван-царевич?

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

50 ≤ n ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10⁵, получат не менее 40 баллов.

Пояснение к примеру

В примере дано n = 150. Мёртвая вода в бутылках объемом 49, 58, 67, 76, 85, 94, 139 и 148. Наибольший подходящий объём — 148.

Примеры тестов

150

148