Задача №113362. Разведение драконов
Лесничий Хогвартса Хагрид собирается заняться разведением драконов, для этого он намерен закупить партию драконьих яиц. С этой целью он отправился в волшебный зоомагазин в Косом переулке.
Хагриду известно, что магическая сила новорождённого дракона зависит от веса яйца дракона в фунтах, а именно, она равняется сумме квадратов цифр в десятичной записи веса. Заметим, что в волшебном мире вес яйца дракона всегда выражается целым положительным числом фунтов.
Естественно, Хагрид желает завести себе драконов как можно большей суммарной силы, но его мотоцикл не сможет поднять груз весом более l фунтов. Ассортимент в волшебном зоомагазине поистине волшебный, поэтому можно считать, что для любого целого положительного веса x , Хагрид может купить в магазине произвольное количество яиц драконов с таким весом.
Напишите программу, которая определит максимальную возможную суммарную волшебную силу драконов, родившихся из яиц, которые Хагрид сможет увезти на своём мотоцикле.
В единственной строке входных данных находится целое число l ( 1 ≤ l ≤ 10 12 ) — максимальный вес груза, который может поднять мотоцикл Хагрида.
Выведите единственное целое число — максимальную возможную суммарную волшебную силу драконов, которых Хагрид будет разводить рядом с Хогвартсом, при условии, что он съездит за яйцами только один раз и увезёт всю покупку на своём мотоцикле.
В первом примере выгоднее всего купить одно яйцо весом 6 фунтов.
Во втором примере выгоднее всего купить два яйца весом 9 фунтов каждое.
6
36
18
162