Задача 63. Поле Чудес ≡

Условие

Не прячьте ваши денежки по банкам и углам,

Несите ваши денежки — иначе быть беде.

И в полночь ваши денежки заройте в землю там,

И в полночь ваши денежки заройте в землю, где?

...

Не горы, не овраги и не лес,

Не океан без дна и берегов,

А поле, поле, поле, поле Чудес,

А поле, поле, поле, поле Чудес,

Поле чудес в Стране Дураков.

Крекс-пекс-фекс…

Булат Окуджава, "Поле чудес в стране Дураков", 1975 г.

Песня из фильма "Приключения_Буратино"

 — Я тебе сейчас объясню. В Стране Дураков есть волшебное поле, — называется Поле Чудес... На этом поле выкопай ямку, скажи три раза: «Крекс, фекс, пекс», положи в ямку столько золотых, сколько захочешь, засыпь землёй, сверху посыпь солью, полей хорошенько и иди спать. Наутро из ямки вырастет небольшое деревце, а на нём вместо листьев будут висеть золотые монеты. Понятно?

 — И сколько же монет вырастет?

 — Зависит от того, сколько закопал. Но ты не переживай — ни одна монетка не пропадёт! Цифры числа зарытых монеток переставляются таким чудесным образом, чтобы получилось как можно большее число. Именно столько монеток утром соберёшь с волшебного деревца. Зароешь одну монетку — одна и вырастит, зароешь 12 — соберешь 21, ну а если, например, 19 не пожалеешь — наутро станешь богачом с 91 золотой монетой! Так что не скупись!

 — А если у меня сейчас ровно n золотых, как мне получить наибольшую прибыль?

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

Единственная строка входного файла содержит натуральное число n — количество денег у Буратино. Он может зарыть их все или разделить на две части и зарыть только одну, а другую спрятать в кармане. Зарытая часть преобразуется согласно описанной операции, спрятанная — не изменится, в сумме они составят новое количество денег Буратино.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите одно натуральное число — наибольшее возможное новое количество денег Буратино.

Ограничения

1 ≤ n ≤ 10¹⁵

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

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

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

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

В первом примере у Буратино 12 монет. Ему выгоднее зарыть их целиком и наутро собрать с дерева 21 монету.

Во втором примере у Буратино 100 монет. Ему выгоднее разделить их на две части: зарыть 19 монет, a в карман спрятать 81 монету. 19 монет превратятся в 91, в сумме с 81 они составят 172.

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

12

21

100

172