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

При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается \(N\) новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно \(Q\) вариантов выбора пары игрушек.

Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек \(i\), \(j\) он хочет проделать следующие операции.

Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом (\(i\)-ю игрушку можно поставить как левее \(j\)-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.

Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось \(O_x\) совпадает с плоскостью стола, а ось \(O_y\), по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.

Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.

Комментарий

Верхний рисунок иллюстрирует исходное размещение игрушек в коробках, а нижние — варианты итогового расположения игрушек (оптимальный вариант слева).

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

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

Изначально пандорианцы обладают запасом золота в 10 золотых слитков. Они решили в один из дней года купить на все это золото воды, а в какой-то последующий день продать всю купленную воду и получить прибыль за счет разницы стоимости. К примеру, если бы стоимость воды в день покупки составляла 1 литр за 4 золотых слитка, а стоимость воды в день продажи – 1 литр за 6 золотых слитков, то пандорианцы могли бы получить купить \(\frac{10}{4}=2.5\) литра воды, а продать они эту воду смогут за \(2.5 \times 6=15\) золотых слитков. Таким образом, прибыль пандорианцев составила бы \(15-10=5\) золотых слитков. Конечно же, пандорианцы хотят максимизировать свой доход в результате этих махинаций. Помогите им выбрать оптимальные дни для покупки и продажи воды!

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

В поисках материала для исследования пандорианцы на своей летающей научной базе прибыли на обыкновенный курортный пляж, до отказа забитый греющимися на солнце туристами. Туристы занимают все доступное место на пляже, образуя, таким образом, прямоугольник размером N × M человек. По пляжу они не перемещаются. То есть, каждый турист однозначно задается своими координатами в этом прямоугольнике: номером ряда, в котором он лежит, и номером в этом ряду.

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

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

Это интерактивная задача. В процессе тестирования программа-решение будет взаимодействовать с использованием стандартных потоков ввода/вывода с программой-интерактором, сообщающей в ответ на координаты двух очередных выбранных туристов цвета их глаз.

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

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

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

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

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

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

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

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