(В. Лашин) На престижном турнире по пауэрлифтингу $M$ тяжелоатлетов соревнуются в силе, поднимая гирю. Спортсмены поочередно подходят к стойке и выбирают вес для дальнейшего подъема. Каждый из них знает свои возможности и, стремясь к победе, выбирает один максимально возможный вес, который способен поднять, из предложенного на мероприятии набора из $N$ разновесных снарядов.

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

Примечание. Гарантируется, что каждый атлет сможет выбрать для себя подходящий вес.

Входные данные:
Первая строка содержит два целых числа: $N$ — количество доступных снарядов и $M$ — количество атлетов $(1\le N\le 50000,1\le M\le 50000)$. Следующие $N$ строк содержат по одному целому числу — веса снарядов (от 1 до 100 000). Последние $M$ строк содержат по одному целому числу — максимальные веса, которые могут поднять атлеты (от 1 до 100 000).

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

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

3 3
50
100
70
60
80
65

При таких исходных данных первый и третий атлеты выберут вес 50, так как они не могут поднять 70 и 100. Второй атлет выберет вес 70, так как он не может поднять 100. Средний вес: (50 + 50 + 70) / 3 = 56. Чаще всего выбирали снаряд с весом 50. Ответ: 56 50.

(Д. Бахтиев, Л. Шастин) На железнодорожной станции ведётся учёт прибывающих и отправляющихся поездов (в минутах, прошедших от начала суток). Станция работает круглосуточно и без перерывов, а администрация станции фиксирует время прибытия и отправления каждого поезда. Поезд считается находящимся на станции с момента его прибытия до момента отправления, т.е. если поезд прибыл в минуту $t$, то всю эту минуту он уже находился на платформе; если поезд уехал в минуту $t$, то в эту минуту на платформе его уже нет.

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

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

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

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

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

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

Пример входных данных
5
12 140 250
44 200 278
13 0 41
84 250 310
11 13 190
Для таких входных данных пиковое количество поездов равно $2$, а количество таких пиков — $3$ (с $13$ до $41$ минуты, с $140$ до $190$ и с $200$ до $278$). Самый длинный пик — третий, сумма номеров поездов для него равна $12+44+84=140$ . Ответ: $3140$.

(Л. Шастин) В одном популярном городе-курорте нашей замечательной страны ведутся срочные работы по укреплению опоры местного автомобильного моста, связывающего разные части города. Для увеличения плотности основного каркаса используют разноразмерные железобетонные балки, из которых по двум сторонам скрепляются и прокладываются платформы длиной $R$ условных единиц. Завод-производитель сварочных изделий предлагает к приобретению $N$ балок, пронумерованных от $1$ до $N$, каждая из которых может быть доступна в нескольких размерах, но продается исключительно в одном экземпляре. В целях экономии государственного бюджета администрация города закупает наименьшее количество балок, суммарной длины которых достаточно для построения вышеописанных платформ.

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

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

В первой строке входного файла находятся два числа: $N$ (натуральное число, не превышающее 10⁵) — количество балок, доступных для покупки, и $R$ (натуральное число, не превышающее 10¹⁰) — длина одной платформы (в у.е). В каждой из следующих $N$ строк находятся размеры соответствующей балки, разделенные друг от друга одним пробелом. Каждая балка может иметь разное количество размеров (от 1 до 15). Все размеры представлены натуральными числами, не превышающими 10⁷. Информация о каждой балке записана на отдельной строке.

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

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

5 63
20 15 30
10 5 14 9 11
40 8
7
50 7 12 9 16 35

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

(Д. Бахтиев) На общегородском учебном совете было принято решение организовать поход классов на премьеру нового полнометражного фильма-триллера «ЭГЕ». Для недопущения массовых беспорядков было решено, что на один сеанс могут попасть ученики только одной параллели одной школы. Также нельзя разбивать одну параллель на несколько сеансов. Порядок, в котором школы и классы выбирают сеанс, строго регламентирован важной коллегией: приоритет отдаётся ученикам более старших классов (то есть сначала выбирают сеанс для учеников 11 класса, затем 10, затем 9 и т.д.) в порядке возрастания номеров школ. По известному количеству сеансов фильма и свободных мест для каждого сеанса определите, какое наибольшее количество параллелей смогут «насладиться» этим шедевром, а также количество учеников, которые увидят этот фильм.
В ответе запишите два целых числа — сначала количество классов, затем количество учеников в этих классах.

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

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

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

3 2
15 10 22
899 11 35
44 3 25
27
26
При таких исходных данных на сеанс смогут пойти два класса: 10 класс (22 человека) из школы №15 и 3 класс (25 человек) из школы №44. Ответ: 2 47

(В. Колчев) Идёт набор в ВУЗ мечты. Абитуриент решает узнать, как обстоят дела с конкурсными списками и на каком он месте. Но вместо упорядоченного документа администрация выгрузила общий список всех подающих документов и приложила логику принятия студентов:
1) На бюджетные места поступают ученики с наибольшей суммой баллов по трём предметам с учетом балла за олимпиаду.
2) Если несколько учеников набрали одинаковую сумму баллов, то в приоритете те, кто набрал больший балл по информатике.
3) Если и таких несколько одинаковых, то смотрят по сумме баллов за математику и олимпиаду.

База данных представляет из себя следующие поля

В ВУЗЕ мечты 300 бюджетных мест. Определите ID ученика, который последний поступает на бюджет и наибольший ID, который не прошел на бюджет но набрал по информатике столько, сколько последний поступивший.

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

Выходные данные
Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи.

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

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

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

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

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

8
2
9
8
4
12
2
10
3

Пример входного файла приведён для набора из восьми игральных карт. При таких исходных данных идеальный карточный домик будет состоять из трёх уровней: {4, 8, 9}, {3, 2}, {2}. Сумма номеров карт, из которых состоит этот домик, равна 28. Ответ: 3 28.

Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID.
Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов
с тремя «двойками» и, наконец, ID студентов, получивших по 2 балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.
Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые 25 % мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее 25 % студентов.
Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».
В ответе запишите два целых положительных числа: сначала ID студента, который занимает последнее место среди студентов с повышенной стипендией, затем ID первого в рейтинговом списке студента, который имеет более двух «двоек».
Входные данные
В первой строке входного файла находится число N, обозначающее количество студентов (целое положительное число, не превышающее 10 000). Каждая из следующих N строк содержит 5 чисел через пробел: ID студента (целое положительное число, не превышающее 100 000) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов N кратно 4 и хотя бы один студент имеет более двух «двоек». Во входном файле все ID различны.
Выходные данные
Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи.
Типовой пример организации данных во входном файле
8
4 4 4 4 4
7 5 5 5 2
10 3 4 4 5
1 4 4 4 3
6 3 5 5 3
2 2 2 2 2
13 2 2 2 3
3 3 3 3 3

При таких исходных данных рейтинговый список ID имеет вид:
4 6 10 1 3 7 13 2. Ответ: 6 13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

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

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

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

Типовой пример организации данных во входном файле
5 20
20000
8000
9000
12000
5000

При таких исходных данных продавец погрузит арбузы весом 12 и 8 кг. Ответ 2 8000.

В супермаркете проводится акция «каждый девятый товар бесплатно». Покупатель, чтобы максимально использовать условие акции, разделил все товары на ленте на группы, по девять товаров в каждой. За каждую группу он собирался заплатить отдельным чеком. В каждой группе из девяти товаров самый дорогой он поместил на девятое место. Однако выяснилось, что программа для кассового аппарата не учитывает расположения товаров на ленте и сортирует цены товаров в чеке таким образом, чтобы стоимость покупки была максимально возможной.

Тогда покупатель разместил товары по-другому.

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

Цены товаров указаны в произвольном порядке.

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

Типовой пример организации данных во входном файле
4
80
50
30
40

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

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

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

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

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

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

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

Два числа: сумма выручки от реализации товара — лидера продаж, а также количество товара этого артикула, оставшееся в наличии.

Типовой пример организации данных во входном файле
8
10 100 1
3 10 0
10 100 0
2 10 1
10 100 0
3 10 1
11 100 0
1 200 0

При таких исходных данных дорогими являются товары стоимостью 100 и 200 рублей. Больше всего было продано товара вида 10. В продаже остался один такой товар. Условию задачи удовлетворяет ответ 200 1.

Отбор кандидатов в матросы происходит по сумме баллов трех экзаменов. На заранее известное количество мест отбираются кандидаты, набравшие большую сумму баллов по результатам трех экзаменов. Все кандидаты, набравшие определенную сумму баллов или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения имеющихся мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше чем вакантных мест, набранная этими кандидатами сумма баллов называется полупроходным баллом. Из числа кандидатов, набравших полупроходной балл, на имеющиеся места принимаются кандидаты, имеющие более высокий балл за собеседование, а при равенстве баллов за собеседование – приоритет имеют кандидаты с наименьшими ID.
Для данного множества кандидатов следует определить ID последнего кандидата с набранным проходным баллом, а также каково количество кандидатов, набравших полупроходной балл.

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

Типовой пример организации данных во входном файле
6 3
1 90 90 90 10
3 60 70 80 8
5 63 60 90 6
8 50 80 100 4
4 40 95 80 7
11 80 63 72 6
При таких входных данных проходной балл равен 230, полупроходной 215, на оставшееся одно место будет назначен кандидат, набравший в сумме 215 баллов и получивший по собеседованию 7 баллов. Ответ для приведённого примера: 8 2.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

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

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

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

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

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

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

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

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

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

100 4
80
30
50
40

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

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

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

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

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

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

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

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

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

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

(PRO100 ЕГЭ) На олимпиаде по программированию задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени s_i. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть t_i минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение каждой задачи участник получает k баллов.

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

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

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

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

Пример входного файла:
6 5
1 2
2 3
1 2
3 1
3 2

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

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

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

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит количество песен N (N ≤ 10000). Каждая из следующих N строк содержит три целых числа, записанные через пробел: время начала (T1) и длительность этой песни (T2) (в секундах 0 < T1 ≤ T2 < 300 000 ), а также 1, если песня "любимая" и 0, если "нелюбимая" соответственно.

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

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

В данном случае наибольшее число песен (4), их временные рамки: (2,3); (3,4); (4,5) или также подходит (4,6); (6,7) , а "нелюбимая" возможная песня, которая играла последней началась в 4, длилась 2, закончилась в 6. Ответ: 4 6

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

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит количество экпериментов N (N ≤ 10000). Каждая из следующих N строк содержит два целых числа: время начала (T1) и время завершения одного экперимента (T2) (в секундах 0 < T1 ≤ T2 < 5 000 000 ).

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

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

В данном случае наибольшее число экпериментов (3) выполнялось в интервале времени между 5 и 7. Ответ: 3 2.