Информатика

(В. Ланская, Р. Ягафаров) В некотором городе существует база данных о зарегистрированных автомобильных нарушениях за последние полгода. Марка каждого автомобиля закодирована как целое число, каждый автомобиль отнесен к одному из трёх классов: эконом, средний, премиум. Возможно, что автомобили одной марки имеют разные классы, это указывает на различные варианты комплектации. В таком случае каждую комбинацию «марка -- класс» следует рассматривать как отдельную марку. На основе этой статистики необходимо определить водители какой марки автомобилей в сумме заплатили больше всего за все нарушения. Если таких марок несколько, то выбирается марка с наибольшим номером, и если и таких марок несколько, то марка с наивысшим классом.

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

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

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

4
6666 750 1
2222 1050 2
3333 550 1
2222 1100 2

При таких исходных данных наибольшую сумму (1050 + 1100 = 2150) заплатили водители марки 2222 класса 2. Ответ: 2222 2150.

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

Входные данные представлены в файле 26-153.txt следующим образом. В первой строке входного файла находится натуральное число 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 рублей. Больше всего (2 шт.) было продано товара артикула 10, в продаже осталась одна единица такого товара стоимостью 100. Ответ: 100 10.

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

Входные данные представлены в файле 26-152.txt следующим образом. В первой строке входного файла находится натуральное число 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 рублей. Больше всего (2 шт.) было продано товара артикула 10 на сумму 200, в продаже осталась одна единица такого товара. Ответ: 200 1.

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

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

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

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

6 3
1 90 90 90 10
3 60 70 80 8
5 65 60 90 6
8 50 80 100 4
4 40 95 80 7
11 80 63 72 6

При таких входных данных проходной балл равен 230, при этом ID последнего кандидата с проходным баллом равен 8. Полупроходной балл (215) -- набрали три человека. Ответ: 8 3.

(И. Карпачев) На улице стоят 5-этажные дома, в каждом из которых 9 подъездов, и на одном этаже каждого подъезда по 8 квартир. Курьерской доставке известны номера домов и квартир, в которые необходимо доставить заказ. Требуется определить наименьший номер дома, в который поступило хотя бы 2 заказа в квартиры, расположенные на одном этаже и в одном подъезде. Для найденного дома определите наибольший номер квартиры, в которую нужно доставить заказ.

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

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

8
101 5
101 16
102 17
102 18
102 124
103 86
103 144
103 145

При таких исходных данных на одном этаже находятся квартиры 17 и 18 в доме 102. Наибольший номер квартиры в этом доме, куда нужно доставить заказ -- 124. Ответ: 102 124.

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

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

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

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

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

Входные данные представлены в файле 26-147.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1500) -- количество заказов. В следующих N строках записаны данные каждого заказа: время приготовления заказа и время, необходимое на доставку и возвращение в центр приготовления (натуральные числа, не превосходящие 1440).

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

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

6
40 70
10 40
85 30
60 30
35 35
40 50

При таких исходных данных ответом 1-й курьер выполнит заказ 10--50. Для доставки партии в течение интервала 35--70 потребуется 2-й курьер, а для партий с интервалами 40--90 и 40--110 потребуются ещё два курьера. Партию в интервале 60--90 сможет обработать уже освободившийся 1-й курьер, и партию в интервале 85--115 -- второй. Ответ: 4 2.

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

Примечание. Прокрастинация -- это постоянное стремление человека откладывать дела и принятие решений на потом. Прокрастинатор -- это человек, страдающий прокрастинацией.

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

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

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

5
2 10
1 20
2 25
2 70
3 24

При таких исходных данных прокрастинатор сможет получить сумму 119, выполнив сначала заказ 4 стоимостью 70, затем заказ 3 стоимостью 25 и в конце заказ 5 стоимостью 24. Ответ: 119 24.

(Н. Кургуз) В поезде, состоящем из M вагонов (вагоны пронумерованы от 1 до M), размещаются N групп людей, в каждой из которых не более 4 человек, среди них могут быть дети. Каждый вагон содержит K четырёхместных купе, а также K двухместных боковых блоков. Каждая группа, в которой больше двух человек, размещается в отдельном купе, а каждая группа из 1 или 2 человек -- в отдельном боковом блоке или купе. Разделять группы нельзя. В первую очередь размещаются группы с большей численностью, а при равной численности приоритет получают те, в которых больше детей. Группы размещаются на первом подходящем месте в вагоне с наименьшим номером. Определите наибольшее количество детей, которых удастся разместить в поезде, а также номер вагона, в котором останется наибольшее количество свободных мест. Если таких вагонов несколько, укажите наименьший номер подходящего вагона.

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

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

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

12
2 2
3 1
3 0
1 0
2 0
4 2
3 2
2 0
4 1
3 1
2 1
3 2
1 0

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

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

Входные данные представлены в файле 26-144.txt следующим образом. Первая строка входного файла содержит натуральные числа N (1 ≤ N ≤ 1000) -- количество клиентов, которые заезжали на заправку в течение дня, и K (1 ≤ K ≤ 10) -- количество заправочных колонок. Каждая из следующих N строк описывает одного клиента и содержит 3 целых числа: время приезда клиента на заправку (количество минут с начала рабочего дня); время, необходимое для заправки, и номер колонки, в которое ему необходимо заправляться (0 означает, что клиент может заправляться на любой колонке). Гарантируется, что никакие два клиента не приезжают одновременно.

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

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

5 2
10 5 0
11 3 1
12 4 0
13 4 1
14 5 0

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

На автозаправке работают две заправочные колонки. Заправиться дизельным топливом можно только в колонке 1, бензином А-76 -- только в колонке 2. Клиент заезжает на заправку и встаёт в очередь к той колонке, в которой есть необходимое ему топливо. Если нужное топливо есть в обеих колонках, клиент выбирает ту, очередь к которой в данный момент меньше. Если обе очереди одинаковые, клиент выбирает колонку с меньшим номером. Если при этом в очереди к выбранной колонке уже стоит 5 или более машин (считая ту машину, которая сейчас заправляется), клиент сразу уезжает.

Входные данные представлены в файле 26-143.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) -- количество клиентов, которые заезжали на заправку в течение дня. Каждая из следующих N строк описывает одного клиента и содержит 3 целых числа: время приезда клиента на заправку (количество минут с начала рабочего дня); время, необходимое для заправки, и номер колонки, в которой ему необходимо заправляться (0 означает, что клиент может заправляться на любой колонке). Гарантируется, что никакие два клиента не приезжают одновременно. Следующая машина может заправляться сразу же, как закончилась заправка предыдущей.

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

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

5
10 5 0
11 3 1
12 4 0
13 4 1
14 5 0

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

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

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

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

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

5
10 150
100 110
131 170
131 180
120 130

При таких исходных данных можно провести максимум два мероприятия, например, по заявкам 2 и 3. Последнее мероприятие может начаться не позднее, чем в момент времени 131, так что максимальный перерыв составит 131 -- 110 = 21 минуту. Ответ: 2 21.

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

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

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

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

4
3 8
1 6
6 9
5 20

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

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

Входные данные представлены в файле 26-140.txt следующим образом. В первой строке входного файла находится натуральное число 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. Ответ: 250 150.

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

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

Входные данные представлены в файле 26-139.txt следующим образом. В первой строке входного файла находятся два натуральных числа: 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-й метр освещается двумя фонарями (если они включены): фонарь {28, 50} и фонарь {15, 50}. Ответ: 3 2.

(Л. Шастин) В отеле есть K жилых номеров, предназначенных для размещения туристов. Все номера пронумерованы, начиная с единицы. Известно время, в которое каждая группа туристов заселяются в номера; время, в которое они планируют их освободить, а также количество номеров, которое потребуется для того, чтобы разместить всю группу туристов сразу. Каждая группа туристов заселяется в свободные номера с наименьшими номерами. Если несколько групп туристов пришли одновременно, то прежде всего обслуживаются группы, которые планируют уйти раньше и для размещения которых требуется меньшее количество номеров. На заселение и выселение туристов уходит одна минута. Со следующей минуты можно заселять в освободившийся номер других туристов. Если группа туристов пришла, но необходимого количества (которого достаточно для заселения их всех) свободных номеров нет -- вся группа уходит, потому что заселиться не может.

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

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

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

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

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

Отсчёт ведётся от начала суток (все числа натуральные, не превышающие 1440), для каждой группы -- в отдельной строке.

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

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

10
5
30 60 5
40 1110 2
30 60 3
60 120 1
120 1440 2

При таких исходных данных первая, вторая, третья и пятая группа туристов смогут заселиться в номера. В первые 29 минут от начала дня все номера были свободны, далее до 40 минуты были свободны 2 номера. С 40-й и до 60-й минуты все номера были заняты на протяжении 21-й минуты, а затем до конца дня хотя бы один из номеров всегда был свободен. Значит, суммарное время, в которое хотя бы один из номеров был свободен, равно 1440 - (60 - 40 + 1) = 1440 - 21 = 1419. Ответ: 4 1419.

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

Входные данные представлены в файле 26-136.txt следующим образом. В первой строке входного файла находится два натуральных числа, не превышающих 10000: N -- количество товаров и M -- средний чек. В следующих N строках записано по два числа: цена товара (она же вид товара) и статус товара (0 -- не продан; 1 -- продан).

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

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

5 60
43 1
90 1
43 0
43 1
90 0

Для данного примера цена самого популярного дорогого товара -- 90 (продан 1 раз), а самого популярного из дешёвых -- 43 (продан дважды). Их сумма = 90 + 43·2 = 176. Продано товаров = 3, всего их в наличии было 5. Осталось = 5 - 3 = 2. Ответ: 176 2.

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

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

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

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

11
5 1
20 30
5 7
20 18
5 30
20 1
20 4
20 16
5 13
20 10
20 24

Для данного примера подходит ряд 5, в котором слева и справа от 7 места есть ровно по 5 свободных мест, и ряд 20, в котором подходят 10-е и 24-е места. В ответ пойдёт ряд с наибольшим номером, содержащий хорошие места, и общее количество хороших мест. Ответ: 20 3.

(Г. Шапошников) Начальник ведет прием граждан. При этом, при формировании очередности приема приняты следующие правила: 1) пенсионеры пользуются преимуществом перед всеми остальными гражданами; 2) женщины пользуются преимуществом перед мужчинами; 3) посетители одной категории принимаются в порядке «живой» очереди. Каждый приём длится определенное время (мин.).

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

Входные данные представлены в файле 26-134.txt следующим образом. Первая строка входного файла содержит два натуральных числа N и T (1 ≤ N ≤ 1000, 1 ≤ T ≤ 10000) -- количество принятых людей и интересующий нас момент времени, соответственно. Каждая из следующих N строк содержит три значения: время, когда посетитель пришел на прием; длительность приема; категория посетителя, одна из трех букв: W (женщина), M (мужчина) и G (пенсионер).

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

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

5 12
1 6 W
4 7 M
5 3 G
8 9 M
11 5 G

При таких исходных данных с 1-й по 7-ю минуту на приёме будет находиться женщина, пришедшая в 1-ю минуту. С 7-й по 10-ю минуту пенсионер, пришедший в 5-ю минуту. С 10-й по 17-ю -- мужчина, пришедший в 4-ю минуту. Всего будет принято 3 человека, из них один мужчина, находящийся на приёме в момент 12. Ответ: 3 1.

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

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

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

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

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

2 3
1 4 2 2
3 6 1 1
5 9 1 2

При таких исходных данных нужно три самоката: два в начале размещаются на парковке 1 и один -- на парковке 2. Одновременно в аренде находятся максимум два самоката (с 3-й по 8-ю минуту включительно). Ответ: 3 1.