Лесничий Хогвартса Хагрид собирается заняться разведением драконов, для этого он намерен закупить партию драконьих яиц. С этой целью он отправился в волшебный зоомагазин в Косом переулке.

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

Естественно, Хагрид желает завести себе драконов как можно большей суммарной силы, но его мотоцикл не сможет поднять груз весом более l фунтов. Ассортимент в волшебном зоомагазине поистине волшебный, поэтому можно считать, что для любого целого положительного веса x , Хагрид может купить в магазине произвольное количество яиц драконов с таким весом.

Напишите программу, которая определит максимальную возможную суммарную волшебную силу драконов, родившихся из яиц, которые Хагрид сможет увезти на своём мотоцикле.

Команда пушистых спасателей сидела без дела в своём дупле, когда неожиданно поступил сигнал бедствия. В считанные мгновения все были на своих местах, и дирижабль бурундучков-спасателей отправился в путь.

Будем считать, что действие происходит на декартовой плоскости. База спасателей расположена в точке ( x ₁ , y ₁ ) , а сигнал бедствия поступил из точки ( x ₂ , y ₂ ) .

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

Разумеется, как настоящий спасатель, Гаечка хочет лететь так, чтобы оказаться на месте происшествия как можно быстрее. Дело осложняется тем, что в небе дует ветер, который влияет на перемещение дирижабля. Согласно прогнозу погоды, в ближайшие t секунд скорость ветра будет характеризоваться вектором ( v _x , v _y ) , а по прошествии t секунд скорость ветра станет равна ( w _x , w _y ) . Данные вектора определяют как направление ветра, так и его скорость. Формально, если дирижабль находится в точке ( x , y ) , его собственная скорость относительно воздуха равна нулю и при этом дует ветер ( u _x , u _y ) , то для любого неотрицательного вещественного числа , через секунд дирижабль окажется в точке с координатами .

Гаечка занята управлением дирижаблем, поэтому она попросила Чипа вычислить, как скоро они смогут быть на месте, с чем он легко справился. Однако Дейл убеждён, что Чип не справился вычислить ответ и назвал случайное значение, лишь бы не ударить в грязь лицом перед Гаечкой. Чтобы пристыдить Чипа, Дейл попросил вас посчитать правильный ответ.

Гарантируется, что скорость ветра в любой момент времени строго меньше максимально возможной скорости дирижабля относительно воздуха.

Гарри Поттер и Тот-Кого-Нельзя-Называть снова сошлись в смертельном поединке. На этот раз они стоят в противоположных концах коридора длины l метров и одновременно пускают в противника свои смертельные заклинания. Известно, что магический импульс заклинания Гарри распространялся со скоростью p метров в секунду, а магический импульс заклинания Сами-Знаете-Кого — со скоростью q метров в секунду.

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

Так как Гарри отлично освоил основы магии, то он знает, что после второго столкновения импульсы исчезнут, а в месте их встречи произойдёт сильный взрыв. Но вот с математикой у юного волшебника проблемы, поэтому он просит вас вычислить расстояние от его позиции до места второй встречи импульсов заклинаний, при условии, что противники стоят на месте в течение всего боя.

Опасаясь приближения мирового экономического кризиса, государства Бермания, Беранция и Берталия заключили союз и разрешили жителям всех входящих в него государств беспрепятственный проход по территории любого из них. Дополнительно было решено построить дороги между государствами так, чтобы из любой точки любого государства можно было добраться до любой точки любого другого государства.

Так как дороги всегда обходятся недёшево, правительства государств новообразованного союза попросили вас помочь им оценить затраты. Для этого вам была выдана карта, которая представляет собой клетчатый прямоугольник из n строк по m клеток в каждой. Любая клетка карты либо принадлежит одному из трёх государств, либо является областью, на которой можно построить дорогу, либо является областью, на которой дорогу построить нельзя. Проходимыми являются все клетки, принадлежащие государствам, а также все клетки, в которых построены дороги. Из любой проходимой клетки можно перемещаться вверх, вниз, вправо и влево, если соответствующая такому перемещению клетка существует и является проходимой.

Требуется построить дороги в минимальном количестве клеток так, чтобы стало возможным добраться из любой клетки любого государства до любой клетки любого другого государства.

Гарантируется, что изначально из любой клетки любого государства можно добраться до любой клетки этого же государства, перемещаясь только по его клеткам. Также гарантируется, что на карте присутствует хотя бы одна клетка каждого государства.