|
На днях первоклассник Вася научился складывать числа.
Ему этот процесс очень нравится, и он складывает всё подряд. Когда все числа
вокруг оказываются сложенными, Вася обращается к своему старшему брату Пете за
новыми числами. После нескольких обращений устав работать генератором случайных
чисел, Петя придумал для Васи занятие, которое может надолго того занять.
Он предложил Васе находить суммы цифр последовательных
чисел - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21 - и так далее, пока Васе не надоест. Вася оказался в восторге от идеи и
принялся за работу. За вчерашний день Вася нашёл суммы цифр каждого из чисел от
1 до 115. Посмотрев на результаты младшего брата, Петя заметил, что суммы цифр
последовательных чисел не являются случайными, часто они идут подряд, но
полностью закономерность он так и не понял.
Чтобы найти закономерности, Петя решил исследовать
крайние случаи, например, какое из чисел даёт максимальную сумму цифр. Данных
для чисел до 115 оказалось недостаточно для окончательных выводов, и Пете
пришла в голову идея для ускорения вычислений использовать вместо братика
компьютер. Поскольку сам он в программировании не очень силён, он обратился за
решением этой задачи к Вам.
В первой строке входных данных находится число N
(1 ≤ N ≤ 2 147 483 647).
Выведите число от 1 до N включительно с максимальной суммой цифр. Если чисел с
максимальной суммой цифр несколько, выведите наибольшее из них.
Обратите внимание, Ваше решение должно выдать ответ не
более чем за одну секунду.
Пример ввода
115
Пример вывода
99
|
