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

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

Входные данные:
В первой строке входного файла находятся два натуральных числа N (N ≤ 1000) и М (М ≤ 1000) - количество экипажей и количество санок соответственно. Следующие N строк содержат числа, обозначающие массы экипажей в граммах, затем идут М строк, где указана максимально допустимая масса группы для конкретных санок. Числа М и N могут быть не равны.

Выходные данные:

Два натуральных числа: сначала максимальное количество экипажей, которые смогут покататься на санках, затем массу самой тяжелой группы в этом случае.

Типовой пример организации данных во входном файле:
5 6
174095
154513
136531
170874
214313
156563
154846
189143
139135
138431
241337

При таких исходных данных максимальное количество экипажей, которые смогут покататься на санках, равно 4, если взять экипажи массой 136531, 154513, 170874 и 174095 соответственно. Максимальный экипаж можно взять равным 214313.

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

На ленте транспортёра детали располагают по следующему алгоритму:

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

Этот алгоритм применяется последовательно для размещения всех N деталей.

Определите номер последней детали, для которой будет определено её место на ленте транспортёра, и количество деталей, которые
будут отшлифованы до неё.

Входные данные

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

Запишите в ответе два натуральных числа: сначала номер последней детали, для которой будет определено её место на ленте транспортёра, затем количество деталей, которые будут отшлифованы до неё.

Типовой пример организации данных во входном файле

5
30 50
100 155
150 170
10 160
120 55

При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте транспортёра деталь 3. При этом до неё будут отшлифованы три детали.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Входные данные:
В первой строке входного файла находятся два натуральных числа N (N ≤ 1000) и М (М ≤ 1000) - количество грузов и количество контейнеров соответственно. Следующие N строк содержат числа, обозначающие массы грузов, затем идут М строк, где указана максимально допустимая масса груза для размещения в конкретном контейнере. Числа М и N могут быть не равны.

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

Типовой пример организации данных во входном файле:
5 6
170
200
130
170
110
150
150
180
130
130
200

При таких исходных данных максимальное количество грузов, которое может быть упаковано в контейнеры, равно 4, если взять грузы массой 110, 130, 170 и 170 соответственно. Максимальная разность двух самых тяжёлых грузов в наборе составит 30, если взять грузы массой 110, 130, 170 и 200 соответственно.

(Д. Бахтиев) Во время матча в расширенной версии игры «Морской бой» велась автоматическая фиксация попаданий по игровому полю. Каждое попадание фиксируется по координатам клетки игрового поля (целые положительные числа x и y) и времени попадания — целому числу t (в секундах от начала матча).

Игровое поле — прямоугольное. Координаты попаданий (x, y) указываются в формате: x — номер строки (считая сверху вниз, от 1 с шагом 1), y — номер столбца (слева направо, от 1 с шагом 1). Некоторые клетки могли быть поражены несколько раз.

Требуется определить такую клетку, в которую было произведено не менее двух попаданий, и среди них — найти ту, в которой минимальный интервал времени между любыми двумя её попаданиями — наименьший. В ответе нужно вывести сумму координаты этой клетки (x + y), а также этот минимальный интервал в секундах. Если таких клеток несколько, выберите среди них клетку с наименьшим номером строки, а если таких тоже несколько — с наименьшим номером столбца.

Входные данные:
В первой строке записано одно целое число N — количество попаданий ($1\le N⩽1000000$). В следующих N строках заданы тройки целых чисел x y t — координаты клетки и время попадания ($1\le x⩽10000$, $1\le y⩽10000$, $0\le t\le {10}^6$).

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

Типовой пример организации входных данных:
7
2 3 10
1 1 3
2 3 15
3 2 20
1 1 10
2 3 17
1 1 6

Для приведённого примера более одного попаданий было в клетки с координатами (2, 3) и (1,1). Минимальный интервал между попаданиями, равный двум секундам, был у клетки с координатами (2, 3). Ответ: 5 2.

(Л. Шастин) Исследователь отправляется в экспедицию через пустыню, чтобы добраться до древнего храма, расположенного на расстоянии R километров от стартовой точки (которая определена первым километром). В начале пути его верблюд полностью отдохнувший и может пройти V километров без остановки. По пути расположены оазисы, в которых можно напоить верблюда и позволить ему восстановить силы, чтобы снова пройти до V километров. Известны координаты N оазисов — километры от начала пути, на которых они расположены, а также запас воды в каждом из них (в у. е.). Каждая 1 у.е. воды эквивалентна 1 километру пути, который может преодолеть верблюд. Определите, какое минимальное количество оазисов придется посетить, чтобы достигнуть древнего храма, а также минимально возможный номер километра расположения оазиса, который получится посетить последний раз.

Входные данные
В первой строке входного файла находится три натуральных числа: N (N ≤ 100 000) – количество оазисов на пути, R (R ≤ 10 000 000) - расстояние от стартовой точки до храма, и V (V < R) – максимальное количество километров, которые может пройти полностью отдохнувший верблюд. В следующих N строках находятся по два числа: расстояние (в километрах) между стартовой точкой и очередным оазисом, и запас воды в каждом из них (в у. е.). Каждое из чисел целое, не превосходящее 10 000 000.
Запишите в ответе два числа: минимальное количество оазисов, которые придется посетить, чтобы достигнуть древнего храма, и, при этих условиях, минимальный возможный номер километра (с оазисом), на котором будет выполнена последняя остановка.

Типовой пример организации данных во входном файле
7 50 20
10 20
19 9
15 11
40 20
31 5
41 10
30 10

При таких исходных данных можно сделать 3 остановки: {15, 30, 41} или {15, 30, 40} или {10, 30, 40}. Ответ: 3 40.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

(Л. Шастин) Частная клиника работает круглосуточно, в режиме 24/7. В течение суток в клинике проводятся медицинские приёмы, каждый из которых характеризуется временем начала и окончания (в миллисекундах, прошедших с начала суток). Считается, что в миллисекунды начала и конца приема он ещё идет. Необходимо проанализировать загруженность врачей за сутки и определить периоды простоя, то есть такие отрезки времени, когда ни один приём не проходил.

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

Входные данные

В первой строке входного файла находится натуральное число N (N < 100 000) - количество приемов, проведенных за сутки.
Следующие N строк содержат пары чисел, обозначающих соответственно время начала и время конца приёма (все числа натуральные, меньшие 86400000).

Запишите в ответе два натуральных числа: сначала найденное количество периодов простоя, а затем их суммарную длительность (в мс).

Типовой пример организации данных во входном файле

6
10 50
100 150
110 155
120 160
130 170
151 170

При таких исходных данных и длительности работы клиники в 200 мс было три периода простоя: в отрезки времени с 0 по 9 мс, с 51 по 99 мс и с 171 по 199 мс . Их суммарная длительность равна (10 - 0) + (100 - 51) + (200 - 171) = 88. Ответ для примера: 3 88.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.

Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон
подходящих коробок составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

В банке дистанционной проверяющей системы имеется более 100 000 заданий. Все задачи пронумерованы начиная с единицы. Эти задания в течение учебного периода решают участники различных курсов. Каждому студенту при регистрации присваивается уникальный идентификатор - натуральное число, не превышающее 1 000 000. Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно из них.
Преподаватель сделал выгрузку результатов за некоторый период времени и выбрал студента, который решил наибольшее количество
задач из банка через одну (одну решил, следующую нет и т.д.).
Определите идентификационный номер студента, который решил наибольшее количество задач через одну, и количество решённых им задач. Если несколько студентов решили одинаковое максимальное количество задач, то укажите студента с наименьшим идентификационным номером.

Входные данные
В первой строке входного файла находится число N - количество зачтённых решений (натуральное число, не превышающее 60 000) за некоторый период времени. Каждая из следующих N строк содержит два натуральных числа, не превышающих 1 000 000: идентификатор студента и номер правильно решённой задачи.

Выходные данные
Два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество успешно решённых задач через одну.

Типовой пример организации входных данных
9
40 3
60 33
60 33
50 124
50 126
50 128
40 4
50 72
50 126
Для приведённого примера студент с идентификационным номером 50 решил наибольшее количество задач через одну (3 задачи).
Ответом является пара чисел: 50; 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

(Л. Шастин) Группа авантюристов хочет добраться до максимально возможно отдаленной от экватора зоны Земли, для чего им предстоит пересечь множество других зон в качестве перевалочных пунктов. При посещении очередной зоны авантюристы затрачивают некоторую сумму денежных единиц на организацию перевала, эта сумма может варьироваться в зависимости от отправной и конечной зоны. Начинает свой путь группа в зоне №1, а изначальные затраты средств равны нулю. Известно, что чем больше номер зоны, тем дальше она расположена от экватора. Из каждой зоны можно попасть только в зоны с большим номером. Имеется $N$ записей, каждая из которых содержит информацию о какой-то зоне: номер текущей зоны, номер переходной зоны, до которой можно добраться отсюда и сумма средств для посещения переходной зоны. Каждая зона может быть представлена в нескольких вариантах с разными переходными пунктами и ценами за переход. Некоторые записи также могут содержать информацию о недостижимых зонах (в которые невозможно попасть, начав движение из зоны №1). Определите номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет $K$ денежных единиц, а также максимальный возможный остаток средств при этих условиях.

Входные данные
В первой строке входного файла находится два натуральных числа: $N(N\le 100000)$ – количество записей о зонах и $K(K\le 1000000)$ - бюджет, которым располагает группа. В каждой из следующих $N$ строк находятся по три числа: номер текущей зоны, номер переходной зоны (в которую можно передвинуться из текущей) и сумма средств, необходимая для перехода. Каждое из чисел натуральное, не превосходящее $1000000$.
Запишите в ответе два числа: номер максимальной зоны, которой могут достигнуть авантюристы, если их бюджет составляет $K$денежных единиц, а также максимальный возможный остаток средств при этих условиях.

Типовой пример организации данных во входном файле
8 100
1 4 20
2 4 30
1 3 10
3 4 5
4 5 5
1 2 10
3 5 20
2 5 50

При таких исходных данных можно достигнуть максимум зоны №5 несколькими способами. Оптимальным вариантом движения будет переход из зоны №1 в зону №3 за 10 ед., затем из зоны №3 в зону №4 за 5 ед. и в конце из зоны №4 в зону №5 за 5 ед. Остаток бюджета при этом составит 100 - 20 = 80 ед. Ответ: 5 80.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки –
подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны меньше длины стороны другой коробки не менее чем на 9 единиц. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000).
В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Типовой пример организации данных во входном файле
5
43
40
32
40
30
Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок,
подходящих для упаковки «матрёшкой», не менее 3 единиц. При таких исходных данных условию задачи удовлетворяют наборы
коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

(М. Попков) В сервисном центре работают K мастерских для ремонта устройств. Некоторые поломки могут быть устранены только в определённой мастерской, некоторые – в любой мастерской. Устройство поступает в центр и ставится в очередь к той мастерской, которая может устранить его проблему. Если поломка может быть устранена в любой мастерской, устройство направляется в ту, в очереди к которой в данный момент меньше единиц техники. Если при этом очереди в несколько мастерских одинаковые, устройство отправляется в мастерскую с наименьшим номером. При этом, если в очереди к выбранной мастерской уже находится 5 или более устройств (включая устройство, которое ремонтируют в данный момент), поступившее устройство сразу отправляют на утилизацию.

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

Входные данные

Первая строка входного файла содержит два целых числа: N (N ≤ 1000) – общее количество устройств, поступивших в сервисный центр за один рабочий день, и K (K ≤ 20) – количество мастерских.

Каждая из следующих N строк описывает одно устройство и содержит 3 целых числа: время поступления устройства в центр (количество минут с начала рабочего дня), время, необходимое для ремонта и номер мастерской, в которую его необходимо направить (0 означает, что ремонт возможен в любой мастерской). Гарантируется, что никакие два устройства не поступают одновременно.

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

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с 1. Гарантируется, что хотя бы одна такая пара в зале есть.

Входные данные

В первой строке входного файла находятся три числа: N – количество занятых мест в зале (целое положительное число,
не превышающее 10 000), M – количество рядов (целое положительное число, не превышающее 100 000) и K – количество мест в каждом ряду (целое положительное число, не превышающее 100 000). В следующих N строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения M, а второе – K).

Выходные данные

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

Типовой пример организации данных во входном файле

7 7 8
1 1
6 6
5 5
6 7
4 4
2 2
3 3

При таких исходных данных ответом является пара чисел 5 и 6. Условию задачи удовлетворяют места 6 и 7 в ряду 5: перед креслами 6 и 7 нет занятых мест и это первая из двух возможных пар в этом ряду. В рядах 6 и 7 искомую пару найти нельзя.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

(Д. Бахтиев) На складе есть K стеллажей для хранения грузов. Все стеллажи пронумерованы, начиная с единицы. Каждый стеллаж представляет собой двумерную сетку размером M × N, где M — количество рядов, а N — количество полок в каждом ряду. Каждая ячейка стеллажа может хранить только один груз.

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

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

Определите, сколько всего грузов будет размещено на складе за 24 часа, и номер ряда первого стеллажа, на котором побывало наименьшее количество грузов. Если таких рядов несколько, укажите номер наименьшего из них.
Входные данные
В первой строке входного файла находятся три числа: K — количество стеллажей на складе (натуральное число, не превышающее 1000), M — количество рядов в каждом стеллаже (натуральное число, не превышающее 100) и N — количество полок в каждом ряду (натуральное число, не превышающее 100).
Во второй строке находится число G — количество грузов, которые поступят на склад (натуральное число, не превышающее 10 000).
В следующих G строках находятся два значения: минута поступления груза и минута, в которую груз заберут (все числа неотрицательные, не превышающие 1440).

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

Пример входных данных:
1 2 2
8
408 1377
1097 1127
225 1349
1085 1332
400 823
100 824
1143 1267
408 1367

При таких входных данных три груза буду размещены в первом ряду, а четыре груза во втором ряду первого стеллажа. Груз 408 1377 не сможет быть размещён на складе. Ответ $7$ $1$

Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме
того, можно получить дополнительное 0 до 10 баллов по итогам собеседования. Каждому кандидату присваивается уникальный идентификационный номер (ID) - натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется
по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм баллов в рейтинговом списке
выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов - с меньшим ID. Минимальная сумма баллов, с которой зачисляются в отряд все, её набравшие, называется проходным баллом. Гарантируется, что всегда есть участники, набравшие проходной балл.

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

Входные данные
В первой строке входного файла находятся два натуральных числа, не превышающих 10 000, через пробел: число N - количество кандидатов и число К - количество мест в отряде. В следующих N строках находятся по 5 чисел через пробел: ID кандидата (натуральное число, не превышающее 100 000) и четыре целых неотрицательных числа - сначала результаты испытаний, затем результат собеседования.
Выходные данные
Два числа: сначала ID кандидата, который последним из рейтингового списка набрал проходной балл, затем количество кандидатов, набравших полупроходной балл.

Типовой пример организации данных во входном файле
6 4
4 80 80 80 0
7 50 80 100 10
11 80 80 70 10
10 100 100 100 2
6 90 90 90 9
2 70 80 80 8
При таких исходных данных рейтинговый список из ID составлен следующим образом: 10 6 7 11 4 2. Два кандидата с баллами 302 и 279 зачислены, проходной балл 279. На оставшиеся два места претендуют три человека, набравшие по 240 баллов, хотя из троих будут зачислены только двое. Таким образом, 240 - полупроходной балл.
Ответ: 6 3

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

(Д. Бахтиев) В магазине «Бахтилэнд» на Светлую среду одновременно действуют две акции. Каждый товар характеризуется своей стоимостью и принадлежностью к категории, которая задаётся натуральным числом.

Для применения акций товары разделяются по категориям следующим образом:

• Если номер категории товара чётный, то для товаров этой категории применяется первая акция:
  На 70% самых дешёвых товаров в данной категории устанавливается скидка 30%, на оставшиеся товары – скидка 20%;
• Если номер категории товара нечётный, то для товаров этой категории применяется вторая акция:
  На 25% самых дорогих товаров в данной категории устанавливается скидка 15%, на оставшиеся товары — скидки нет;

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

Входные данные.

Первая строка входного файла содержит натуральное число N – количество товаров (500 ≤ N ≤ 10000).
Далее следует N строк, каждая из которых содержит два натуральных числа:

• первое число – стоимость товара (натуральное число, не превышающее 10000),
• второе число – номер категории товара (натуральное число, не превышающее 100).

Типовой пример организации данных во входном файле

7
80 2
45 2
50 1
40 8
34 33
48 7
100 13

При таких исходных данных, при продажи всех товаров по первой акции магазин получит 123 рубля, а по второй — 217 рублей. Общая выручка — 340 рублей. При этом по первой акции недополученной выручкой будет 42 рубля (165 - 123), а по второй 15 рублей (232 - 217). Разность между недополученной выручкой по первой и второй акциям составила $|42-15|=27$ рублей. Ответ: 340 27.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

(М. Попков) Магическая типография королевства занимается поставкой книг и журналов в волшебные ларьки и древние библиотеки. Для этого было выделено большое транспортное облако, а сами заказы распределены по ящикам, наполненным магическими страницами. Известно количество всех ящиков, а также их массы, измеренные в зачарованных единицах (зе). Также известно, что транспортное облако имеет ограничение по весу, так как его магическая тяга не бесконечна, и оно может увезти только определенное количество ящиков. Для перевозки была придумана система: ящики с массой от 310 зе до 320 зе включительно, содержащие редкие заклинания и древние манускрипты, грузятся в первую очередь, чтобы магические энергии не иссякли в пути. На основе имеющейся информации определите наибольшее число ящиков, которое транспортное облако может увезти за один раз (при условии, что первыми погружены ящики от 310 до 320 зе включительно) и их наибольшую массу, при условии, что размещено наибольшее число ящиков.

Входные данные:

Первая строка: первое значение — общее количество ящиков (натуральное число, не превышающее 1000), второе значение — грузоподъёмность транспортного облака (натуральное число, не превышающее 10000). Следующие строки — массы ящиков (натуральные числа, не превышающие 1000).

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

Пример:

6 841
315
150
110
190
135
190

Первым делом нужно взять ящик массой 315 зе. Для оставшихся ящиков у нас есть 526 зе. Выберем ящики весом 190, 190 и 135 зе и получим общую наибольшую массу погрузки – 830 зе. Для примера ответом будет 4 830.

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

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

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

Входные данные.

В первой строке входного файла находятся два числа: M – максимальная масса, которая может быть погружена на поезд (натуральное число, не превышающее 10000) и N – количество бидонов (натуральное число, не превышающее 1000). В следующих N строках находятся массы всех имеющихся бидонов (все числа натуральные, не превышающие 200), каждое в отдельной строке.

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

Пример входного файла:

300 4

200

110

150

120

При таких исходных данных можно погрузить максимум два бидона. Возможные массы этих двух бидонов 110 и 120, 110 и 150 или 120 и 150. Заведомо поезд не сможет увезти один бидон с массой 200, поэтому ответ для приведённого примера: 2 1.

(М. Попков) В эльфийскую башню совета поступило N заявок на проведение собраний мудрейших эльфов. Каждая заявка содержит время начала и время окончания заседания (в минутах от начала суток). Если время начала одного собрания совпадает с временем окончания другого, то провести можно оба. Однако, если время начала одного собрания меньше времени окончания другого, то провести можно только одно из них. Определите максимальное количество собраний, которое может состояться в башне совета, и самое позднее время окончания последнего из этих собраний.

Входные данные

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

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

Типовой пример организации данных во входном файле

5
10 150
100 110
131 170
131 180
120 130

При таких исходных данных можно провести максимум три собрания, например, по заявкам 2, 3 и 5. Башня совета освободится самое позднее на 180-й минуте, если будут проведены собрания по заявкам 2, 4 и 5.