Каждый год в честь дня города в Южно-Берляндске проводится открытая эстафета. В конкурсе участвуют команды из \(k\) человек, в процессе эстафеты участники команды должна посетить \(n\) контрольных пунктов.

Контрольные пункты пронумерованы от \(1\) до \(n\), место старта обозначим как пункт \(0\). Соревнование проходит следующим образом: первый участник из команды стартует из пункта \(0\), пробегает по некоторым \(a_1\) ранее не посещенным контрольным пунктам, возвращается в пункт \(0\) и передает эстафету второму участнику. После этого второй участник пробегает какие-либо \(a_2\) ранее не посещенных контрольных пунктов, возвращается и передает эстафету следующему. Эстафета продолжается, пока последний участник не посетит \(a_k\) ранее не посещенных контрольных пунктов и не вернется на старт. Передача эстафеты происходит мгновенно. Цель команды — пробежать эстафету как можно быстрее.

Учащиеся Южно-Берляндского бегового училища решили заранее подготовиться к состязанию. Они раздобыли план соревнования, из которого они узнали числа \(a_i\), а также выяснили про каждую пару пунктов, за какое время можно успеть добежать от одного до другого. Все участники команды перемещаются с одинаковой скоростью, поэтому это время не зависит от того, кто побежит между этими пунктами.

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

Лера часто ездит по работе из Санкт-Петербурга в Москву и обратно. Так как дела у нее всегда срочные, добирается до места назначения она всегда на Сапсане. Как известно, в каждом вагоне Сапсана расположено ровно \(n\) мест, а именно \(\frac{n}{2}\) рядов по два места в каждом (\(n\) четное).

Однажды по пути домой после деловой встречи у Леры не было соседа, и ей стало скучно. Поэтому она задалась вопросом: сколько максимум человек можно посадить в вагон Сапсана, чтобы ровно у половины людей был сосед. Помогите Лере ответить на этот сложный вопрос.

В батальоне непонятного назначения действует правило, что у каждого офицера должно быть не менее \(a\) и не более \(b\) звезд на погоне, при этом ни у каких двух офицеров не должно быть равного числа звезд.

В результате понижения в звании в батальон сослали офицера Й, у которого на погоне до понижения было \(c\) звезд. Теперь командиру батальона положено лишить его части звезд на погоне, в результате чего число звезд на его погоне должно стать строго меньше \(c\).

Командир батальона исследовал вопрос и выяснил, что минимальное положительное число звезд, которое можно удалить с погона офицера Й, чтобы правило выполнялось, равно \(d\), а максимальное — \(e\). Командир незамедлительно сообщил об этом офицеру Й.

Теперь офицера Й заинтересовал вопрос: какое минимальное и максимальное количество офицеров могло быть в батальоне до его прибытия? При этом командир батальона сам офицером батальона не является, и на его погонах изображены специальные загадочные символы, а не звезды.

Недавно Женя устроился в компанию «Гуглекс», и сегодня его первый рабочий день. Женя живет на другом берегу реки и для проезда на работу решил воспользоваться паромом. Неожиданно он обнаружил, что съехать с парома на шоссе — не такая уж простая задача.

Машины на съезде с парома стоят в \(n\) полос, в \(i\)-й из которых стоит \(c_i\) машин, а непосредственно перед съездом находится светофор. Раз в минуту он включается зеленым и несколько машин с парома съезжают на берег. Женя заметил, что за один зеленый сигнал светофоров количество машин, которые могут успеть проехать со всех полос, суммарно не превосходит \(k\).

Понимая, что он не один такой, кому не нравится стоять в пробках, Женя ввел понятие «злости водителя». Злость водителя в некоторый момент времени равна количеству машин,которые стоят перед ним в этот момент в той же полосе. Например, если в полосе стоит 3 машины, то у водителя, чья машина находится ближе всего к светофору, злость равна 0, у следующего — 1, а у последнего — 2. Как настоящий программист, Женя сразу же начал думать, как можно оптимизировать процесс съезда с парома.

Оптимальным ему показался следующий вариант: в каждой полосе перед съездом поставить шлагбаум, который будет за один зеленый сигнал светофора пропускать только определенное количество машин. А именно, \(i\)-й полосе будет сопоставлено целое число \(k_i\) — максимальное количество машин, которые могут съехать за один зеленый сигнал. Сумма всех \(k_i\) должна быть равна \(k\).

В качестве параметра оптимизации Женя выбрал суммарную злость всех водителей за все время съезда. Каждую минуту после очередного включения зеленого света просуммируем злость всех еще не покинувших паром водителей. Просуммируем получившиеся величины за все минуты, пока хотя бы один водитель еще находится на пароме. Женя хочет подобрать \(k_i\) таким образом, чтобы получившаяся величина была минимальна.

Пока Женя стоит в пробке, помогите ему написать программу, находящую оптимальные \(k_i\), чтобы он смог оправдаться перед начальством за опоздание в первый же рабочий день.

Ивану с детства нравились газеты. У него даже была мечта стать главным редактором газеты. Однажды ему представился шанс осуществить свою мечту. Чтобы устроиться на работу в издательство, ему необходимо выполнить тестовое задание — сверстать рекламное объявление.

Задано поле шириной \(W\) и высотой \(H\). Объявление должно состоять из одной или нескольких строк, в которых необходимо разместить в заданном порядке \(N\) слов. Про \(i\)-е слово известно, что при печати в стандартном масштабе оно занимает прямоугольник шириной \(a_i\) и высотой \(b_i.\)

Чтобы объявление выглядело красиво, все слова в нем должны быть напечатаны в одном масштабе. При печати в масштабе \(k\) размеры всех слов умножаются на \(k\). Если исходно слово занимало прямоугольник \(a_i \times b_i\) , то при печати в масштабе \(k\) оно занимает прямоугольник размером \((k \cdot a_i) \times (k \cdot b_i)\). Кроме того, если в строке более одного слова, то все слова в ней должны иметь одинаковую высоту. Разумеется, ни одно слово не должно выходить за границы поля.

На рисунке приведен пример красивого объявления с тремя словами.