e-olymp
Задачі

Максимум

Максимум

На днях пешокласник Василько навчився додавати числа. Йому цей процес дуже подобається, і він додає все підряд. Коли всі числа навколо виявляються доданими, Вася звертається до свого старшого брата Петра за новими числами. Після декількох звертань втомившись працювати генератором випадкових чисел, Петро придумав для Василька заняття, яке може надовго того відволікти.

Він запропонував Васильку знаходити суми цифр послідовних чисел — 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 включно з максимальною сумою цифр. Якщо чисел з максимальною сумою цифр декілька, виведіть найбільше з них.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
115
Вихідні дані #1
99