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

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

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

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

Первая строка входного файла содержит целое число \(N\) \((N \leqslant 2000)\) — количество заявок на уборку снега. Следующие \(N\) строк содержат пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость. Каждое из чисел натуральное, не превосходящее \(10~000.\) Гарантируется, что конец участка не выходит за пределы дороги.

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

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

\(5\)
\(1 \,\, 1000\)
\(1001 \,\, 1000\)
\(2001 \,\, 2500\)
\(4501 \,\, 500\)
\(4501 \,\, 1500\)

При таких исходных данных будет выполнено не более \(4\) заявок. Могут быть выполнены заявки с номерами \(1, \, 2, \, 3\) и \(4\) или заявки с номерами \(1, \, 2, \, 3\) и \(5.\) Ответ: \(4 \,\, 3999.\)

В магазине продаётся \(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.\)

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

На грузовом космическом корабле необходимо перевезти на МКС контейнеры, имеющие одинаковые габариты и разные массы. Общая масса всех этих контейнеров превышает грузоподъёмность космического корабля. Количество грузовых мест на космическом корабле не меньше числа контейнеров, назначенных к перевозке.

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

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

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

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

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

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

\(100 \,\, 4\)
\(80\)
\(30\)
\(50\)
\(40\)

При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров — \(30\) и \(40,\) \(30\) и \(50\) или \(40\) и \(50.\) Контейнеры с массами \(50\) и \(80\) могут быть не перевезены. Ответом для приведённого примера является пара чисел \(2\) и \(130.\)

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

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

Алгоритм формирования рейтинга выглядит следующим образом:

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

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

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

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

В магазине для упаковки подарков есть \(N\) кубических коробок из материалов двух видов. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Все коробки, которые будут использованы для упаковки подарка, нумеруются с единицы, начиная с той коробки, в которой будет находиться подарок. Одну коробку можно поместить в другую, если они изготовлены из разных материалов, а длина её стороны хотя бы на \(K+2000\) единиц меньше длины стороны другой коробки, где \(K\) – порядковый номер помещаемой коробки. Известны длины сторон и материал коробок, имеющихся в наличии. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка и минимально возможную длину стороны самой большой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

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

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

\(6\)
\(43 \,\, 1\)
\(41 \,\, 0\)
\(39 \,\, 0\)
\(38 \,\, 1\)
\(26 \,\, 0\)
\(24 \,\, 1\)

Пример входного файла приведён для шести коробок.

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

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

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

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

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

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

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

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

\(2 \,\, 5\)
\(70\)
\(60\)
\(30 \,\, 30\)
\(40 \,\, 960\)
\(59 \,\, 1\)
\(61 \,\, 939\)
\(1010 \,\, 430\)

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

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