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

Сегодня мы будем помогать Анте, тренеру команды Загреба. Анте привёз N игроков на чемпионат, причём у каждого игрока есть своя сила p _i и своя выносливость d _i . Для каждого игрока известно, что его «суммарное игровое время» не превышает величину его выносливости. «Суммарное игровое время» игрока — это суммарное количество времени, которое игрок провёл на поле. То есть, если игрок сначала провёл на поле X минут, а потом Y минут, то его «суммарное игровое время» равно X + Y минут.

В каждой момент времени у команды есть её сила — сумма сил всех шестерых игроков, находящихся на поле. Общая сила команды Z — это сумма сил команды во все минуты игры. То есть, если игра длилась 3 минуты и в первую минуту сила команды была 15 , во вторую — 12 , а в третью — 14 , то общая сила команды — 15 + 12 + 14 = 41 . Анте знает, что чтобы победить, надо максимизировать общую силу команды. Но Анте — не очень талантливый тренер, поэтому он просит вас помочь ему составить оптимальное расписание выхода команд, чтобы Z было максимально. Гарантируестя, что можно составить расписание так, чтобы в каждый момент на поле было по 6 игроков.

Обратите внимание, что в хорватском хоккее все игроки могут заменять друг друга, и вратаря нет, ведь так игра становиться гораздо веселее.

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

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

Мы можем представлять двор Дональда как бесконечную систему координат, а простыни - как прямоугольники, параллельные осям координат. Выстрелы Кима могут быть представлены как точки в этой системе.

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

Мирко нужно купить землю, чтобы построить дом для своей семьи. Он присмотрел K участков. Для простоты будем считать, что участок представляет собой поле с N строками и M столбцами, N × M клеток в сумме.

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

Так как поворачивать газонокосилку непросто, Мирко хочет минимизировать количество поворотов газонокосилки. Для каждого из K участков земли ему нужно знать минимальное число поворотов для покоса. Помогите Мирко с этой задачей.

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

Вам дан список S из k разрешённых слов. Так же вам даны буквы Зига за первые n ходов. На каждую из этих ходов найдите слово, которое Заг должен сказать.

Домагой смотрит на руку Мате, играя в очень упрощённую версию игры «Ханаби». Для простоты скажем, что Мате держит в руке N карт, пронумерованных числами 1, 2, ..., N в каком-то фиксированном порядке (каждое из чисел от 1 до N соответствует ровно одной карте). Как и в настоящей игре, Мате не может менять порядок карт.

Домагой указывает Мате на подотрезок последовательности карт, после чего Мате «разворачивает» этот отрезок карт.

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

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