Задача I. Вандал в Суссексе ≡

Условие

Эта история случилась с нами в Брайтоне, куда Холмса пригласили на несколько дней в качестве свидетеля для дачи показаний в суде над Суссексским серийным убийцей. Мой друг остался в гостинице, а я прошелся по городку, нанес визит своему коллеге, с которым вместе учился, и уже под вечер зашел в местную библиотеку взять что-нибудь почитать на сон грядущий.

Неприятным сюрпризом для меня стало отсутствие одного листа в самом конце книги. Он был отрезан самым аккуратнейшим образом. Наутро я вернул книгу в библиотеку и выразил свое недоумение. Книгохранитель заметно расстроился.

 — Еще одна...

 — Еще одна?

 — Да, мистер Ватсон. Приносим Вам свои извинения. Дело в том, что в прошлом году один из наших сотрудников был пойман на вандализме. Он вырезал из книг одну из страниц и терпеливо ждал, когда другие сотрудники или читатели замечали это. Тогда книга списывалась, а поскольку именно он отвечал за утилизацию... Дома при обыске полиция обнаружила сотни списанных изданий, естественно с уже вклеенными страницами. Некоторые ценные экземпляры он даже продавал через Интернет. К сожалению, вырезанные листы он хранил где-то в другом месте, и, чтобы на суде ему не прибавили срок, божился, что больше никаких книг испортить не успел. Но время идет, а читатели продолжают находить испорченные книги, вот как Вы сейчас.

 — Что же Вы не проверите все оставшиеся книги?

 — На это требуется много времени и сил, а штат у нас небольшой. Если бы мы точно знали номера страниц, которые вырезал этот негодяй, проверка была бы несложной. У меня есть подозрение, что этот человек вырезал листы, пользуясь определенным правилом. Но все, к кому я обращался, не могли найти никакой закономерности.

Попросив у библиотекаря формуляры испорченных книг с указанием номера вырванного из них листа, я поспешил к Холмсу и рассказал о местной проблеме. Шерлок обрадовался возможности занять свой мозг интересной задачей, обложился подушками, табаком, формулярами и погрузился в размышления.

 — Есть!  — воскликнул он примерно через 15 минут.  — Закономерность есть!

В библиотечной книге было ровно n листов, по одной странице с каждой из двух сторон (на k-м по счету листе располагались страницы с номерами 2 × k − 1 и 2 × k). При очередной проверке оказалось, что из книги вырезан лист, сумма цифр номеров страниц на котором максимальна. По известному n определите эту сумму.

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

Единственная строка входного файла содержит натуральное число n — первоначальное количество листов в книге.

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

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

Ограничения

1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰

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

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

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

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

В примере книга первоначально состояла из 10 листов (20 страниц). Вырван был предпоследний лист, сумма цифр двух номеров страниц на нем равна 1 + 7 + 1 + 8 = 17 — больше, чем на всех остальных.

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

10

17