Экзамены и диагностики

(Л. Шастин) Меню бургерной включает 1000 различных блюд, которым присвоены коды от 0 до 999. В отчёте фиксируют время начала и окончания приготовления каждого заказа. Если запись о заказе некоторого блюда встретилась первый раз -- это время начала приготовления; если второй раз, значит, он уже приготовлен (может случиться так, что некоторые заказы по каким-то причинам не были приготовлены). Готовить несколько блюд с одним номером одновременно нельзя.

Входные данные представлены в файле 26-86.txt следующим образом. В первой строке входного файла записано натуральное число N (1 ≤ N ≤ 100 000) -- общее количество строк с данными. В каждой из следующих N строках записана пара чисел, разделённых пробелом: время (в минутах от начала работы бургерной) и код блюда (0..999).

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

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

8
60 5
40 1
90 5
45 5
20 2
55 1
10 2
50 5

Наибольшее количество заказов -- три -- было приготовлено за час времени от 10 до 70 (70 -- 10 = 60), это есть часовой максимум. Блюдо с кодом 1 в среднем готовилась 55 -- 40 = 15 минут, блюдо 2 готовилась 20 -- 10 = 10 минут, а блюдо 5 -- (30 + 5)/2 = 17,5 минут.

Ответ: 3 5.

(М. Шагитов) В одном из конференц-залов города Н проводится научная конференция. Известно, какие места в зале уже забронированы для участников конференции из других городов и для участников конференции из города Н. Найдите ряд с наибольшим номером, в котором есть ровно сто свободных мест подряд между участниками из других городов, а также хотя бы пятьсот мест, занятых участниками из города Н. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию.

Входные данные представлены в файле 26-85.txt следующим образом. В первой строке входного файла записано натуральное число N -- общее количество занятых мест (1 ≤ N ≤ 600 000). В каждой из следующих N строках находятся по целых числа, не превышающих 25 000. Первые два числа -- это номер ряда и место в ряду, занятое участником конференции (натуральные числа). Если третье число равно 0, то место занято участником из города Н, а если оно равно 1, то участником из другого города.

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

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

15
1 1 0
1 3 1
1 5 0
1 7 1
1 8 0
2 3 1
2 8 1
2 9 0
2 10 0
3 1 0
3 2 1
3 6 1
3 7 0
3 8 0
3 9 0

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

В 3-м ряду есть 3 свободных места подряд между участниками из других городов (выделены жёлтым) и 4 места заняты участниками из города Н. В этом ряду 2 места заняты участниками из других городов (выделены зеленым). Ответ: 3 2.

(99 баллов) В университете Инфаполис учится N групп студентов, для обучения которых используется N аудиторий. Известно количество студентов в каждой группе и количество мест в каждой аудитории. Группа всегда занимает целую аудиторию (группы не объединяются). Администрацию университета заинтересовал вопрос: сколько существует способов рассадить все группы по аудиториям, и сколько групп (по одной) вмещаются в самую маленькую аудиторию.

Входные данные представлены в файле 26-84.txt следующим образом. В первой строке записано натуральное число N (1 ≤ N ≤ 100 000) -- количество аудиторий (и количество групп). В следующей строке записано N натуральных чисел -- количество студентов в каждой группе (целые числа, не превышающие 1 000 000). В третьей строке записано N натуральных чисел -- количество мест в каждой аудитории (целые числа, не превышающие 1 000 000).

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

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

3
2 3 4
5 6 3

При таких исходных данных всего есть 4 варианта размещения (A5: 2 означает, что в аудитории вместимостью 5 человек размещается группа из 2-х человек):

1) A5: 2, A6: 4, A3: 3,

2) A5: 4, A6: 2, A3: 3,

3) A5: 4, A6: 3, A3: 2,

4) A5: 3, A6: 4, A3: 2.

В самой маленькой аудитории (на 5 человек) можно разместить одну из двух 2 групп (из 2-х или 3-х человек). Ответ: 4 2.

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10000 на 10000 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 10000) и номер позиции в строке (целое число от 1 до 10000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, -- тёмной.

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

Входные данные представлены в файле 26-82.txt следующим образом. В первой строке входного файла записано целое число N -- количество частиц, попавших на экран. В каждой из следующих N строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.

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

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

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

При таких исходных данных в строке 2 имеются две точки в чётных позициях (3 и 5). Ответ: 2 2.

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10000 на 10000 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 10000) и номер позиции в строке (целое число от 1 до 10000). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, -- тёмной.

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

Входные данные представлены в файле 26-82.txt следующим образом. В первой строке входного файла записано целое число N -- количество частиц, попавших на экран. В каждой из следующих N строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.

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

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

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

При таких исходных данных в строке 1 имеются две точки в чётных позициях (2 и 4). Ответ: 2 1.

(Е. Джобс) В лесополосе высаживают плодовые деревья рядами на одинаковом расстоянии друг от друга. Между соседними саженцами в одном ряду расстояние 10 метров. В каждом ряду высаживают разные виды плодовых деревьев. Через какое-то время с помощью аэросъемки определяют, какие саженцы прижились, а какие -- нет. Для успешного перекрестного опыления необходимо, чтобы дерево было на расстоянии не более 20 метров от прижившегося дерева того же вида, иначе оно не будет плодоносить. Определите, какое минимальное количество деревьев нужно посадить, чтобы все деревья могли плодоносить, и номер ряда, в котором необходимо дополнительно посадить максимальное количество деревьев.

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

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

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

7
1 3
1 5
1 8
2 2
2 5
3 1
3 9

В этом случае достаточно посадить 4 дерева в позициях (1, 7), (2, 4), (3, 3) и (3, 7). Наибольшее количество деревьев (2) нужно посадить в 3-м ряду. Ответ: 4 3.

(Досрочный ЕГЭ-2022) В лесополосе осуществляется посадка деревьев: саженцы высаживают рядами на одинаковом расстоянии. Спустя некоторое время с помощью аэросъемки выясняют, какие саженцы прижились. Необходимо определить ряд с максимальным номером, в котором есть подряд ровно K неприжившихся саженцев при условии, что справа и слева от них саженцы прижились. В ответе запишите сначала наибольший номер ряда, затем наименьший номер неприжившегося саженца.

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

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

6 3
40 30
40 34
50 125
50 129
50 64
50 68

В примере требуется найти 3 подряд идущих неприжившихся саженца. Ответ: 50 65.

([PRO100 ЕГЭ](https://stepik.org/users/388343822)) Для проведения ЕГЭ требуются наблюдатели. На сайте профи.ру есть список наблюдателей и время, в которое они могут работать. Требуется нанять как можно меньше наблюдателей, чтобы в каждый момент экзамена за учениками присматривал хотя бы один наблюдатель, при этом смена первого наблюдателя произошла как можно позже, с момента старта ЕГЭ.

Входные данные представлены в файле 26-78.txt следующим образом. В первой строке содержится количество наблюдателей N, время начала ЕГЭ -- start и время окончания -- end, то есть время проведения ЕГЭ -- это полуинтервал [start, end). В следующих N строках содержится по два числа a, b, где a -- время начала, b -- время окончания работы наблюдателя, то есть наблюдатель работает в течение полуинтервала [a, b).

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

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

5 2 10
1 4
1 3
3 8
7 10
10 11

Наблюдение полностью обеспечивают наблюдатели, работающие в полуинтервалы [1, 4), [3, 8),  [7, 10). Время работы первого наблюдателя с начала экзамена 4 - 2 = 2. Ответ: 3 2.

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

Входные данные представлены в файле 26-77.txt следующим образом. В первой строке входного файла записано число N -- количество наклеек, которые собрал Иван (натуральное число, не превышающее 10 000). В следующих N строках записано по два числа: сначала номер страницы в альбоме (натуральное число от 1 до 30), затем номер наклейки на странице (натуральное число от 1 до 8). Запишите в ответе два числа: количество наклеек, которых не хватает Ивану для заполнения альбома, и номер страницы, на которой отсутствует наибольшее количество наклеек. Если таких страниц несколько выберите последнюю из них.

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

10
1 1
1 2
1 3
1 4
1 6
1 6
1 8
2 4
3 1
3 3

При таких входных данных будем считать, что Ивана интересуют только страницы с 1 по 3.

На первой странице ему не хватает 2 наклеек; на второй странице не хватает 7 наклеек; на 3 странице не хватает 6 наклеек (всего 15 наклеек, больше всех не хватает на странице 2). Ответ: 15 2.

(А. Кабанов) На производстве станок с ЧПУ обрабатывал некоторый набор деталей. В каждый момент времени станок может обрабатывать только одну деталь. Каждая деталь изготавливалась в определённый промежуток времени с момента начала рабочего дня. Простоем считается временной участок, в течение которого не обрабатывается ни одна деталь. Инженер решил узнать, какова суммарная длительность простоев за день и какова длительность наибольшего простоя. Общая длительность рабочего дня L секунд.

Входные данные представлены в файле 26-76.txt следующим образом. В первой строке входного файла находятся два числа через пробел: число L -- общая длина рабочего дня (натуральное число, не превышающее 10⁹) и число N -- количество изготовленных деталей (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа через пробел. Первое число -- время начало обработки от начала рабочего дня (натуральное число, не превышающее 10⁹). Второе число -- время окончания обработки (натуральное число, не превышающее 10⁹).

Запишите в ответе два числа: суммарную длительность простоев за день и длительность наибольшего простоя.

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

1000 4
600 750
350 450
0 350
950 1000

При таких условиях имеется два простоя: 450--600; 750--950. Их суммарная длительность 350, наибольший имеет длину 200. Ответ: 350 200.

(А. Кабанов) Автомат фиксирует пассажиров некоторого автобуса по ходу рейса. У каждого пассажира фиксируется время входа и выхода с момента начала рейса. Необходимо узнать максимальное количество пассажиров, одновременно находящихся в автобусе, и общее время, когда в автобусе был хотя бы один пассажир. Временем входа и выхода в автобус пренебречь.

Входные данные представлены в файле 26-75.txt следующим образом. В первой строке входного файла находится число N -- общее количество пассажиров (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа. Первое число -- время входа пассажира от начала рейса (натуральное число, не превышающее 1 000 000). Второе число - время выхода пассажира от начала рейса (натуральное число, не превышающее 1 000 000).

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

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

7
10 40
50 130
70 130
75 90
120 170
140 170
150 180

В приведённом примере пассажиры были в временных отрезках 10-40 и 50-180. Максимальное количество пассажиров одновременно 3. Ответ: 3 160.

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 640 на 480 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 640) и номер позиции в строке (целое число от 1 до 480). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, -- тёмной.

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

Входные данные представлены в файле 26-73.txt следующим образом. В первой строке входного файла записано целое число N -- количество частиц, попавших на экран. В каждой из следующих N строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.

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

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

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

При таких исходных данных имеется две цепочки чередующихся точек: в позициях 2, 3 и 4 строки 1, и в позициях 3, 4 и 5 строки 2. Обе они включают по 2 светлых точки, минимальный номер строки -- 1. Ответ: 2 1.

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 640 на 480 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 640) и номер позиции в строке (целое число от 1 до 480). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, -- тёмной.

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

Входные данные представлены в файле 26-73.txt следующим образом. В первой строке входного файла записано целое число N -- количество частиц, попавших на экран. В каждой из следующих N строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.

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

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

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

При таких исходных данных имеется три цепочки светлых точек: в позициях 2 и 3 строки 1, в позициях 4, 5 и 6 строки 2 (это самая длинная цепочка!) и точка в позиции 6 строки 3. Ответ: 3 2.

(Е. Джобс) Игра «Заполни поле» заключается в том, чтобы заполнить прямоугольное поле, разбитое на квадраты. Игрок хочет написать программу, которая определила бы сколько есть позиций, в которые можно поместить горизонтальные блоки из четырех квадратов.

Входные данные представлены в файле 26-72.txt следующим образом. В первой строке записаны три числа N, M, K -- размер поля по горизонтали, размер поля по вертикали и количество занятых на поле квадратов. В каждой из следующих K строк записана пара чисел -- номера строки и столбца занятого квадрата.

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

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

7 6 10
1 1
1 5
2 5
2 6
3 1
3 7
5 2
6 3
6 5
6 7

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

Расположить линию из четырех квадратов можно в 9 позициях (2;1), (3; 2), (3; 3), (4; 1), (4; 2), (4; 3), (4; 4), (5; 3), (5; 4). Максимальное количество позиций (4), в которых можно расположить фигуру, в 4 ряду. Ответ: 9 4.

(А. Кабанов) Маркетплейс с оптового склада каждый день отправляет заказанные товары в точки выдачи. Маркетплейс имеет множество видов различных товаров, каждый из которых имеет какой-то вес. Для отправки склад выделяет транспорт таким образом, чтобы отправить как можно больше товара каждого типа, но вес товаров одного типа не должен превышать S. Нужно определить, сколько всего товаров останется на складе и тип товара с самым большим остатком. Если таких товаров несколько, вывести товар с наименьшим кодом.

Входные данные представлены в файле 26-71.txt следующим образом. В первой строке входного файла записаны два числа, разделённые пробелом пробел: число N -- количество доступных товаров (натуральное число, не превышающее 10000) и число S -- вес, не более которого можно отправить каждый тип товара (натуральное число, не превышающее 10⁸). В каждой из следующих N строк записаны по два числа, разделённые пробелом: код товара (натуральное число, не превышающее 10⁹) и его вес (натуральное число, не превышающее 10⁵). Известно, что количество различных кодов товаров в файле не превышает тысячи.

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

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

8 13
150 8
237 3
237 6
150 4
237 5
237 6
150 3
150 3

При таких исходных данных имеется всего два вида товаров (с кодами 150 и 237). Товаров с кодом 150 можно погрузить три штуки (3, 3 и 4), останется 1 штука (8). Товаров с кодом 237 можно погрузить две штуки (за 3 и 5), останется 2 штуки (6 и 6). Ответ: 3 237.

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

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

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

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

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

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

4
1
4
1
11

При таких исходных данных два слитка не подходят под условие: 4 и 11. Для исправления будут заказаны слитки весом 1 и 4 (2 слитка общим весом 5). Ответ: 2 5.

(А. Кабанов) Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором наибольшее количеством подряд идущих мест, таких что все они уже распределены (заняты). В ответе запишите два целых числа: номер ряда и наибольшее количество подряд занятых мест.

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

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

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

10
5 5
5 6
5 7
16 9
16 3
16 6
20 23
20 28
20 29
20 30

В данном примере максимальное количество подряд идущих занятых мест равно 3 (5 ряд места 5, 6, 7 и 20 ряд места 28, 29,30). Ответ: 20 3.

(Л. Шастин) Компьютер был заражён вирусами. Супервирусами называются самые опасные вирусы, уровень опасности которых превышает средний уровень опасности всех имеющихся. Нужно определить, какое максимальное количество вирусов можно удалить за заданное время по следующим правилам:

-- необходимо удалить как можно больше супервирусов;

-- нельзя удалять два и более супервируса подряд;

-- нельзя удалять супервирус последним;

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

Входные данные представлены в файле 26-68.txt следующим образом. Первая строка входного файла содержит количество записей N и общее время T, отведённое на удаление этих вирусов. Каждая из следующих N строк содержит два целых числа: уровень опасности вируса и время, которое требуется для его удаления.

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

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

5 50
7 13
9 20
4 3
8 9
5 5

Средний уровень опасности равен 6.6, значит, суперопасными считаются вирусы с уровнем опасности >= 7. Удаляем сначала супервирус 8-9, далее обычный вирус 4-3, потом снова суперопасный 7-13, затем обычный 5-5. Обычных вирусов не осталось, значит, суперопасные тоже удалять нельзя. Итого удалено 4 вируса. На удаление супервирусов затрачено времени 9 + 13 = 22. Ответ: 4 22.

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

Входные данные представлены в файле 26-66.txt следующим образом. Первая строка входного файла содержит количество записей N и время K. Каждая из следующих N строк содержит два целых числа: время начала и время завершения обработки одного запроса (в миллисекундах).

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

Пример входного файла (для заданного диапазона от 1000 до 6000):

6 1000
1300 2200
0 3700
1300 5700
0 0
5000 0
1800 3400

В данном случае наименьшее число запросов (2) выполнялось в интервале времени между 1000 и 1300, между 3700 и 5000, а также от 5700 до 6000 (общее время 300 + 1300 + 300 = 1900). Ответ: 2 1900.

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

Входные данные представлены в файле 26-66.txt следующим образом. Первая строка входного файла содержит количество записей N и время K. Каждая из следующих N строк содержит два целых числа: время начала и время завершения обработки одного запроса (в миллисекундах).

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

Пример входного файла (для заданного диапазона от 1000 до 6000):

6 1000
1300 2200
0 3700
1300 5700
0 0
5000 0
1800 3400

В данном случае наибольшее число запросов (5) выполнялось в интервале времени между 1800 и 2200. Ответ: 5 400.