Маленький Влад обожает играть в популярную игру Bota-2 на своем компьютере. На днях разработчики сообщили о выходе её продолжения под названием Bota-3. Разумеется, Влад тут же её приобрёл, но оказалось, что компьютер Влада слишком старый для этой игры, поэтому он отправился в магазин за обновлением для него.

В магазине Влад увидел n видеокарт, i -я из которых имеет свою мощность a _i , выражаемую целым положительным числом. Для того, чтобы игра точно заработала, Влад решил купить не одну, а несколько видеокарт и объединить их мощности по новейшей технологии. Для использования этой технологии одна из видеокарт выбирается в качестве ведущей, а все остальные видеокарты подключаются к ней в качестве вторичных. Для корректной работы этой конструкции необходимо, чтобы мощность каждой видеокарты была кратна мощности ведущей видеокарты. Для обеспечения совместимости мощность каждой вторичной видеокарты может быть понижена до любого меньшего целого положительного значения. При этом мощность опорной видеокарты должна оставаться оригинальной, то есть не может быть уменьшена.

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

Арсений уже совсем взрослый и самостоятельный. Мама решила оставить его на m дней в одиночестве и уехать отдыхать в тёплые страны. Перед этим она наготовила ему много еды, оставила достаточное количество карманных денег и постирала всю одежду.

Однако за десять минут до отъезда в тёплые страны ей пришла в голову мысль, что Арсению надо оставить точную инструкцию, какую одежду надевать в какой из дней её отсутствия. Арсений живёт в очень необычной семье, в которой вся одежда пронумерована: например, n носков Арсения имеют различными целые номера от 1 до n . Поэтому всё, что потребовалось его маме, это указать для каждого дня два числа l _i и r _i — номера носков, которые надо надеть в i -й день на левую и правую ногу соответственно (разумеется, l _i не совпадает с r _i ). Каждый носок покрашен в один из k цветов.

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

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

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

У Миши сегодня день рождения, и в честь этого события он решил погулять с друзьями. Поскольку день рождения Миши в морозный зимний день, дети отправились играть со снегом на поляне. Они уже заготовили n снежных шаров и были готовы лепить из них снеговиков, как вдруг Миша сообщил, что ему нравятся только красивые снеговики . В представлении Миши красивый снеговик — снеговик, состоящий из как минимум k снежных шаров, идущих в порядке невозрастания радиуса снизу вверх. Причём радиусы двух соседних шаров должны отличаться не менее чем на d сантиметров.

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

Винни-Пух отправился в очередную Экспедицию по Лесу!

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

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

Вы решили помочь медвежонку и хотите определить по карте Леса, могло ли такое случиться.

Где-то в Москве в очередной раз построили новый дом: красивый, современный и многоэтажный. Он состоит из ровно \(n\) жилых этажей, пронумерованных от \(1\) до \(n\) снизу вверх, и подземной парковки, являющейся нулевым этажом.

Дом уже был почти готов к сдаче в эксплуатацию, но вот незадача — в самый ответственный момент по всему зданию прорвало водопроводные трубы, в результате чего многие этажи залило водой. К моменту, когда все трубы были заделаны, на \(i\)-м этаже находилось \(w_i\) литров воды.

Также из-за того, что при строительстве дома все средства ушли на отделку фасада, а на перекрытия между этажами был пущен самый дешёвый материал, оказалось, что между этажами ощутимо протекают потолки. В частности, пропускная способность пола \(i\)-го этажа составляет \(v_i\) литров воды в час.

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

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