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

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

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

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

Определите сколько деталей будет отшлифовано, и деталь с каким номером окажется на позиции с номером K на ленте транспортёра.

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

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

Типовой пример организации данных во входном файле
5 3
30 50
100 155
150 170
10 160
120 55
При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Отшлифовано будет четыре детали. На третьей позиции будет находиться деталь с номером 2.
Ответ: 4 2.

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

(Л. Шастин) Дальнобойщику необходимо добраться до пункта выгрузки товаров, для чего ему предстоит преодолеть путь длиной R километров. В начале пути топливный бак грузовика полон и вмещает в себя такое количество бензина, которого достаточно, чтобы проехать V километров. Имеется информация о количестве заправочных станций на пути и километрах, на которых они расположены. Определите, какое минимальное количество раз придется заправиться дальнобойщику, чтобы достигнуть пункта выгрузки товаров, а также минимально возможный километр, на котором получится заправиться в последний раз.

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

Типовой пример организации данных во входном файле
7 50 23
45
15
23
48
29
7
46

При таких исходных данных можно заправиться 2 раза: {7, 29} или {15, 29} или {23, 29} или {23, 46}. Ответ: 2 29.

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

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

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

В первой строке файла содержится количество наблюдателей 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
Ответ: 3 2.

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

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

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

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

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

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

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

100 4
80
30
50
40

При таких исходных данных можно перевезти максимум 2 посылки. Их возможные объёмы: 30 и 40, 30 и 50 или 40 и 50. Наибольший объём посылки из перечисленных пар — 50, поэтому ответ для приведённого примера: 2; 50.

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

(М. Попков) У Санта-Клауса и его команды для упаковки подарков есть N кубических коробок двух цветов. Самой привлекательной для детей считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д, при этом их цвета обязательно должны чередоваться. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 7 единиц меньше длины стороны другой коробки. Коробка с нечетной длиной стороны - красная, с четной - синяя. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

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

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

6
43
40
33
28
40
29

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

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 29, 40 и 43 или 33, 40 и 43 или 28, 33, 40, 43 соответственно, т.е. наибольшее количество коробок равно 4, а наибольшая длина стороны самой маленькой коробки равна 28.

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

(PRO100 ЕГЭ) Петя играет в компьютерную игру "Кучи камней". Всего в игре есть N уровней. Для каждого уровня известно, какой нужен skill для его прохождения. Кроме того, после прохождения каждого уровня skill Пети увеличивается. Для каждого уровня указано, на сколько увеличится skill, после его прохождения. Уровни можно проходить в любом порядке.

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

Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 10000) – количество уровней в игре и натуральное число K (K ≤ 1000) – начальный skill Пети. Следующие N строк содержат пары чисел, первое число обозначает skill необходимый для прохождения уровня, а второе число – на сколько увеличится skill Пети, после прохождения этого уровня. Каждое из чисел натуральное, не превосходящее 100000.

Запишите в ответе два числа: максимальное количество уровней, которые Петя сможет пройти, и его финальный skill.

Типовой пример организации данных во входном файле
5 6
10 15
8 1
1 2
27 10
9 2
При таких исходных данных Петя сможет пройти четыре уровня:, (10, 15), (8, 1), (1, 2) и (9, 2). Его финальный skill будет равен 26.

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

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

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

В первой строке файла находиться натуральное число N – количество всех шаров в наборе. В следующих N строках по два числа – позиция центра шара на ленте и радиус шара.

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

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

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

5
6 2
3 1
4 2
12 4
8 2

При таких исходных данных, игроки смогут разместить на ленте максимум 3 шара: (3, 1) -> (6, 2) -> (12, 4). Тогда минимальная конечная отметка ленты для такого размещения шаров будет равна 16.

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

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

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

Дан входной файл, который в первой строке содержит натуральное число N – количество новых роботов. Затем N строк содержащих целые числа c_i – минимальная емкость батарейки для робота с номером i. Затем следует натуральное число M – количество видов батареек, предоставленных для закупки. Далее в каждой из M строк содержится пара натуральных чисел a_i и b_i - емкость батарейки и ее цена соответственно.

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

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

3

1

2

4

5

1 10

1 5

8 6

2 4

4 9

При таких исходных данных минимальная стоимость закупки будет составлять 14 (для первого и второго робота необходимо купить батарейки емкостью 2 и стоимостью 4, а для третьего робота емкостью 8 и стоимостью 6) 4 + 4 + 6 = 14. Цена самой дорогой купленной батарейки составит 6.

(Л. Шастин) Министерство транспорта планирует обновить всё дорожное покрытие на шоссе длиной R километров. Часть работ была проведена ещё в прошлом году, потому дорожники, чтобы не выполнять двойную работу, определили вдоль шоссе отрезки дороги, которые уже отремонтированы, причем информацию о каких-то километрах занесли в реестр несколько раз. Каждый отрезок задаётся километровой меткой старта и конца. Назовём «непригодными» участками шоссе такие непрерывные отрезки, которые не отремонтированы и расположены между отремонтированными участками либо между краем шоссе и ближайшим отремонтированным участком. Определите количество "непригодных" отрезков трассы, а также наибольшую длину среди отрезков трассы, которые были отремонтированы ещё в прошлом году.

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

Типовой пример организации данных во входном файле
5 50
10 39
15 35
12 25
30 41
45 48

При таких исходных данных три участка являются "непригодными": 1-9, 42-44, 49-50. Длина наибольшего из уже отремонтированных участков равна 31 (10-41). Ответ: 3 31.

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

(Л. Шастин) Организация планирует закупить N товаров у поставщика. Магазин же, в свою очередь, предоставляет оптовому покупателю скидку на K любых товаров, причем размер скидки варьируется от товара к товару и может различаться. Организация, пользуясь случаем, выбирает, на какие из товаров сделать скидку, таким образом, чтобы заплатить как можно меньше. Определите сумму, которую заплатит организация за N товаров, а также, при этих же условиях, минимальную возможную стоимость товара, купленного со скидкой.

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

Типовой пример организации данных во входном файле
7 3
100 20
200 55
150 50
700 50
50 80
125 88
800 80

При таких исходных данных организация купит товары {125, 88}, {800, 80} и {700, 50} со скидкой. Ответ: 1025 125.

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

(Л. Шастин) Проспект длиной K метров освещён N фонарями, стоящими вдоль него. Администрация города выяснила, что количество включённых фонарей избыточно для освещения всего проспекта – какие-то из них можно выключить, чтобы сэкономить на тратах электроэнергии, таким образом, что проспект все равно останется освещён полностью. Входной файл содержит данные о метках начала и конца отрезков, освещаемых фонарями. Определите, какое максимальное количество фонарей можно выключить так, чтобы проспект остался освещён полностью, а также общее количество фонарей, которые, если их включить, освещают K-й метр проспекта.

Примечание: начало проспекта определено 1-м метром, конец – K-м метром.

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

Типовой пример организации данных во входном файле
5 50
1 30
28 50
20 40
1 10
15 50
При таких исходных данных можно выключить 3 фонаря: второй, третий и четвёртый. K-й метр может быть освещен 2 фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.

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

(PRO100 ЕГЭ) Школьник Петя готовится к ЕГЭ по нескольким предметам в разных онлайн школах. В каждой онлайн школе уроки ведутся онлайн в определённое время. У Пети есть расписание всех уроков. Он хочет посетить как можно больше уроков, при этом посещать уроки он хочет целиком. Ему не важно по какому предмету они будут. Его интересует только количество посещённых уроков.

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

Входные данные
В первой строке файла находится натуральное число N – общее количество уроков. В следующих N строках содержатся по два числа – время начала start, и время окончания end урока. Длительность урока: [start, end).

Выходные данные
Выведите два числа – максимальное количество уроков, которые можно посетить и время селфи.

Типовой пример организации данных во входном файле
4
3 8
1 6
6 9
5 20

Ответ: 2 6.

При таких исходных данных Петя может посетить максимум два урока [1, 6), [6, 9), время селфи – 6.

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

(Л. Шастин) Гостевой зал одного из ресторанов города включает в себя K столиков, которые сохранены в базе данных по номерам от 1 до К.

В call-центр ресторана звонят клиенты, желая забронировать столик. В отчете предоставлена информация о звонках, которые происходили за вчерашний день. Известно время, на которое каждый клиент хочет забронировать столик на сегодняшний день, ID-номер конкретного столика, им выбранного, и время, в которое был совершен текущий звонок. При этом, согласно регламенту ресторана, любой столик бронируется ровно на 120 минут. Администратор выделяет для клиента столик, если на то время, в которое клиент желает пребывать в ресторане, не назначено другой, ранее сделанной брони. Но если тот столик, который хочет забронировать клиент, уже занят, тогда администратор выделяет для клиента другой столик с наименьшим ID-номером, среди всех тех, что свободны в рассматриваемое время. Каждый столик считается свободным со следующей минуты после окончания предыдущей брони, время на его уборку не входит в учёт. Если свободных столиков нет, то администратор просит прощения у клиента и сообщает, что он не может записать его.

Длительность рабочего дня ресторана составляет 1440 минут. Последняя минута возможной брони столика = 1320.

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

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

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

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

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

5
2
130 2 20
150 2 10
570 1 300
180 2 50
600 1 200

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

Ответ для примера: 4 1.

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

(М. Ишимов) Входной файл содержит информацию о заказах клиентов на доставку продуктов. В каждом заказе известно время создания заказа (в минутах от начала суток) и длительность доставки от пункта сбора заказов до клиента (совпадает с длительностью возвращения курьера в пункт сбора заказов). Доставкой занимаются $K$ курьеров, каждый может доставлять из пункта сбора заказов за раз только один заказ.
Каждый заказ обрабатывается в порядке очереди следующим образом:

– если в момент поступления заказа все курьеры заняты, он будет выполнен с задержкой первым освободившимся курьером;
– сбор заказа происходит в течение 2 мин при наличии свободного курьера;
– курьер доставляет заказ до клиента и после выполненного заказа курьер возвращается в пункт сбора заказов;
– с момента прихода в пункт сбора курьер может приступить к доставке следующего заказа.
Определите, сколько заказов в течение 24 ч будут выполнены с задержкой и в какую минуту завершится последний за сутки заказ, выполненный без задержки.

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

В первой строке входного файла находится два натуральных числа $K(K\le 1000)$ и $N(N\le 1000)$ – соответственно количество курьеров и количество заказов.
Каждая из следующих $N$ строк содержит два натуральных числа: указанное в заявке время создания (в минутах от начала суток) и необходимое время для доставки соответствующего заказа, каждое из которых не превышает 1440.
Запишите в ответе два числа: количество заказов, выполненные с задержкой, и минута завершения последнего за сутки заказа, выполенный без задержки.
Типовой пример организации данных во входном файле
2 5
675 90
716 90
723 72
818 62
1394 45
При таких исходных данных третий и четвёртый заказы будут выполнены с задержкой. Второй заказ будет последним за сутки выполненным заказом без задержки и завершится в 808 мин.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

​(PRO100 ЕГЭ) Входной файл содержит расписание показа фильмов во всех кинотеатрах Москвы за весь прошедший месяц. Определите суммарное время, в течение которого показывался хотя бы один фильм.

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

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

Типовой пример организации данных во входном файле
4
100 200
200 250
400 500
420 480

При таких исходных данных хотя бы один фильм показывался в промежутки времени [100; 250) и [400; 500). Суммарное время равно (250-100) + (500-400) = 250. Максимальный непрерывный отрезок времени, в течение которого показывался хотя бы один фильм равен 250-100 = 150.

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

Входной файл содержит сведения о заявках на проведение мероприятий в конференц-зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. Если время окончания одного мероприятия совпадает со временем начала другого, то провести можно оба. Определите, какое максимальное количество мероприятий можно провести в конференц-зале и каков при этом максимально возможный перерыв между двумя последними мероприятиями.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и время окончания мероприятий. Каждое из чисел натуральное, не превосходящее 1440.
Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).
Типовой пример организации данных во входном файле
5
10 150
100 120
131 170
150 180
120 130
При таких исходных данных можно провести максимум три мероприятия, например, мероприятия по заявкам 2, 3 и 5. Максимальный перерыв между двумя последними мероприятиями составит 20 мин., если состоятся мероприятия по заявкам 2, 4 и 5.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

Первая строка входного файла содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее ${10}^6$.

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

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

4
14
10
13
13

Ответ для приведённого примера: 4 40.

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

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

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

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

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

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

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

При таких исходных данных было два пика посещаемости: в отрезки времени со 130 по 150 минуты и со 151 по 155 минуты. Число посетителей в момент пика посещаемости равно 4.

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