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

В автопарке компании есть \(n\) маршруток, \(i\)-ая маршрутка номинально вмещает \(a_i\) пассажиров. По договору с департаментом транспорта города компания обязана обслуживать \(m\) маршрутов. Накопленная статистика говорит, что оптимальнее всего, если \(j\)-ый маршрут обслуживает такси номинальной вместимостью \(b_j\) пассажиров. Каждая маршрутка приписывается не более чем к одному маршруту, каждому маршруту приписывается не более одной маршрутки.

Разумеется, каждый уважающий себя диспетчер при назначении маршруток на маршруты старается минимизировать потери, которые бывают следующими:

• если \(i\)-ая маршрутка обслуживает \(j\)-ый маршрут, то компания теряет \(|a_i-b_j|\) у.е., так как чем меньше заполнено такси, тем больше не используются его возможности, а чем больше переполнено такси, тем чаще его приходится ремонтировать;
• от каждой простаивающей маршрутки, то есть такой, которой не назначен ни один маршрут, компания несет убыток \(p\) у.е.;
• компании приходится платить штраф \(q\) у.е. департаменту транспорта за каждый не обслуживаемый маршрут.

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

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

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

Понравилась мысль такая царю Тридевятого царства. Подумал он ввести и у себя такие порядки. Собрал царь советников своих, и говорит: подготовьте мне список дней, в которые гулять можно. Только не на год, а на \(N\) дней вперед — посмотрим, дескать, что получится; понравится — сделаем круглогодичным.

И вот вчера принесли советники царю список. Но вот незадача: каждый советник свой список приготовил, да еще и обоснование предложил, какой праздник в какой из этих дней надо отмечать. И у всех советников праздники важные, но у всех — разные! Царь думал-думал и решил: а возьмем их все — объединим предложения советников! Если какой-то день есть в списке хотя бы одного советника, то объявим этот день праздничным, и пускай народ гуляет! Глядишь, и не будет недовольных.

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

Пусть, например, четыре советника сразу предложили сделать некоторый день (пускай день 5) праздничным. Тогда перенесем три из этих четырех праздников на дни 6, 7 и 8 — так, что праздничными будут дни с 5 по 8 включительно. А если оказывается, что, например, день 7 тоже предложен в качестве праздничного кем-нибудь из советников, то перенесем этот праздник еще дальше — на день 9.

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

Сеть компьютерных салонов «ХТТП» представлена в городе Н. двумя магазинами. Руководство Н-ского отделения сети решило реорганизовать витрины, на которых представлены ноутбуки. В каждом из двух магазинов на витрине должны быть представлены \(N\) моделей ноутбуков, выставленные в ряд от касс вглубь помещения магазина. Маркетологи каждого из магазинов уже определили порядок, в котором на витрине должны быть расположены эти модели (эти порядки в двух магазинах, конечно же, могут быть разными).

На витрины надо выставлять специальные, выставочные, образцы ноутбуков, с соответствующим программным обеспечением, показывающим рекламу, и т.д. В распоряжении администрации компьютерных салонов есть две версии специализированного ПО: работающие под управлением операционных систем Windows и Linux. Соответственно, каждый из выставочных образцов ноутбуков должен иметь предустановленной ровно одну из этих систем.

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

Но при этом возникла проблема. По требованиям Федеральной антимонопольной службы, компьютерные салоны не должны предоставлять преимущества ни одной из операционных систем. Начальство сети «ХТТП» знает, как проходит проверка на соответствие этой норме законодательства. Инспектор антимонопольной службы идет по магазину начиная от касс вдоль витрины с ноутбуками, считает отдельно количество встреченных ноутбуков с Windows и Linux, а также модуль разности этих чисел (т.е. на сколько ноутбуков с одной системой он встретил больше, чем ноутбуков с другой системой). В некоторый момент он останавливается и говорит: «Ага!». Это значит: слишком у вас большой дисбаланс между операционными системами, поэтому платите штраф. Размер штрафа пропорционален разнице (взятой по модулю) количества ноутбуков с разными системами, которые увидел инспектор.

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

Например, пусть \(N=5\): в магазинах должны быть выставлены пять моделей ноутбуков. Будем нумеровать модели ноутбуков от 1 до 5. Пусть в первом магазине маркетологи определили, что оптимальный порядок ноутбуков следующий (от касс вглубь зала):

2 4 1 3 5,

а во втором магазине —

3 1 2 5 4.

Тогда, если закупить ноутбуки моделей 1, 3 и 4 с операционной системой Windows, а 2 и 5 — с Linux, то порядок операционных систем в магазинах будет следующий (от касс вглубь зала):

L W W W L,

W W L L W.

Тогда, если, например, инспектор придет в первый магазин и просмотрит первые четыре ноутбука, то он скажет: «Ага!», и выпишет штраф за то, что он увидел Windows-ноутбуков на два больше, чем Linux. Аналогичный результат будет, если он придет во второй магазин и просмотрит только первые два ноутбука.

А если закупить ноутбуки 2 и 3 с системой Linux, а 1, 4, 5 — с Windows, то порядок операционных систем будет следующий:

L W W L W,

L W L W W,

и в какой бы магазин не пришел инспектор, и сколько бы ноутбуков он не посмотрел, разница Windows- и Linux-ноутбуков не будет превосходить по модулю 1, и это и будет оптимальным вариантом для руководства сети. (Напомним, что инспектор всегда начинает осмотр магазина от касс и идет вглубь магазина вдоль ряда с ноутбуками).

Вчера у Васи был счастливый день: он наконец дописал программу всей своей жизни! И, недолго думая, он тут же запустил ее на Самом Главном Тесте.

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

Вася понял, что напрасно он не тестировал программу. Ведь Самый Главный Тест очень сложный — в нем есть \(N\) отдельных подзадач, и каждую из них надо решить. Конечно, надо было бы начать тестирование с меньшего количества подзадач, но ведь Вася — очень умный программист! И он абсолютно уверен, что его программа корректно решила все подзадачи, кроме какой-то одной. Вот только Вася не знает, какой именно.

Вася может изменять Самый Главный Тест, отключая в нем те или иные подзадачи. Он надеется, что, если среди отключенных будет та подзадача, на которой его программа не работает, то получившийся тест его программа спокойно пройдет. Но вот проблема: программа работает долго, а подзадач много, и потому, если отключать задачи по одной, то придется очень долго искать нужную. А Вася очень хочет узнать, где ошибка, уже завтра!

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

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