(А.Богданов) В некотором вузе N абитуриентов поступают на некое направление на М мест. Абитуриенты сдали ЕГЭ по русскому языку, профильной математике, физики и/или информатике. В зачет идет 3 экзамена. Если сданы и физика, и информатика, то в зачет идёт максимальный балл из двух предметов. Часть выпускников еще не подала оригиналы документов, что отмечено в исходных данных первым полем (0/1). Необходимо определить гарантированно проходной балл.

Входные данные: в первой строке N – кол-во выпускников, M – кол-во мест на направление и далее N строк для каждого абитуриента, в которых первое число 0/1 (отсутствие/наличие оригиналов документов) и далее 3 или 4 оценки: баллы по русскому, профилю, физике и/или информатике.

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

- проходной балл с учетом наличия оригиналов документов (на момент запроса)
- проходной балл без учета наличия оригиналов документов (верхняя оценка)

Пример:
6 2
0 60 80 90 80
1 61 80 90 80
0 62 80 90 80
1 63 80 90
0 64 80 90
1 65 80 90

С учетом наличия оригиналов документов будут зачислены абитуриенты с баллами 235 и 233. Проходной 233. Без учета документов 235 и 234. Проходной 234.

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

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

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

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

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

5
32
13
85
52
46

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

(3 * 85 + 52 + 46 = 353; 3 * 85 = 255)

(PRO100 ЕГЭ) В супермаркете проводится акция «каждый шестой товар в чеке за полцены». У покупателя есть 100 000 рублей. Какое максимальное количество товаров может купить покупатель, если он сам выберет расположение товаров в чеке?

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

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

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

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

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

5

4

80

30

50

40

Пример входного файла приведён, для покупателя со ста сорока рублями и для акции «каждый второй товар в чеке за полцены». При таких исходных данных ответом на первый вопрос будет число 5 (Пример расположения товаров в чеке: 40 50 4 80 30, сумма покупки: 40 + 50/2 + 4 + 80/2 + 30 = 139), на второй вопрос число 1 (140 - 139 = 1).

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

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

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

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

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

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

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

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

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

4

80

30

50

40

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

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

Определите, сколько будет закуплено товаров типа S и сколько денег останется.

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

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

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

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

В ответе укажите объем свободного места в кэше (в МБ) до удаления первого файла из кэша. И количество файлов в кэше после размещения последнего файла.

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

Выходные данные: Первое число – объем свободного места в кэше (в МБ) до удаления первого файла. Второе - количество файлов в кэше после размещения последнего файла.

Пример:

6 100

30

10

40

50

10

20

До удаления первого файла в кэше будет 100-(30+10+40)=20 МБ. А после кэширования последнего файла в кэше будет 3 файла (50+10+20)

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

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

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

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

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

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

7 3

2

6

7

8

8

10

15

Для приведённого примера можно составить трассы 6 + 7 + 8, 6 + 8 + 8, 7 + 8 + 8, 8 + 8 + 10, максимальная пропускная способность возможна при варианте 8 + 8 + 10, ответом является пара чисел: 8 10.

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

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

7

13 600 700

17 300 400

23 250 800

27 550 200

30 750 350

37 900 200

42 850 170

Число в первой строке обозначает количество позиций в отчете, каждая из которых имеет свой уникальный номер ID, равный первому числу в последующих строках. Второе и третье число обозначают цену на товары, ID которых отличаются от прописанного в текущей строке на -10 и +10, соответственно. Если к ID одного товара можно прийти несколькими способами, в таком случае стоит взять цену, которая встретилась в файле раньше для этого ID. Если подходящего под условия ID не нашлось, значит товара нет в продаже. Необходимо определить:

А) Какое наибольшее количество имеющихся товаров можно закупить, при условии, что цена каждого следующего купленного товара должна отличатся не менее, чем на 50+R, где R - порядковый номер товара в корзине в случае его покупки. Нумерация всех товаров в чеке начинается с 1.

Б) Какая наименьшая цена возможна у купленного товара.

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

Приведем решение для примера выше. По имеющимся данным можно сказать о цене товаров c ID, равными 13, 17, 23, 27 и 37, стоят которые будут 250, 550, 700, 400 и 200, соответственно. Из имеющихся товаров, согласно условию, можно купить товары с ценами 200, 400, 550 и 700. Таким образом, можно купить 4 товара, а минимальная цена у купленного товара равно 200. Ответ: 4 200

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

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

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

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

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

5
43
40
32
40
30

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

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

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

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

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

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

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

5

43

40

32

40

30

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

При таких исходных данных условию задачи удовлетворяют наборы колец с диаметрами 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество колец равно 3, а диаметр самого маленького кольца равен 32.

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

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

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

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

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

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

8

50 R

48 G

43 B

40 R

36 B

34 G

22 B

17 R

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

При таких исходных данных условию задачи удовлетворяет набор коробок 50, 43, 34, 22, то есть количество коробок равно 4, а длина стороны самой маленькой коробки 22.

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

На карте представлена следующая схема формы записи:

6

3 20 17

6 15 16

7 17 40

5 19 81

9 21 13

11 14 18

Первое число N (1 < N < 300) обозначает количество работающих станций. Далее имеется N строк, содержащих по 3 числа, разделенных пробелом. Первое число в идущих ниже строках обозначает текущий уникальный ID-номер станции, а последующие два числа (всегда различных по величине) указывают на расстояние до станций, ID которых численно отличаются на 1 и 2 в большую сторону соответственно. По имеющимся данным необходимо узнать, до какой станции с максимальным ID-номером можно доехать, если начинать со станции, имеющей наименьший ID, и какое минимальное расстояние можно преодолеть, если при поездке на каждую следующую возможную станцию необходимо всегда выбирать кратчайший маршрут. В качестве ответа указать два числа - сначала минимальное расстояние, а затем номер станции.

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

Приведем решение задачи для примера выше. Из станции 3 можно отправиться на станцию 4 или 5, но поскольку станции с ID = 4 нет, то поехать можно только на станцию c ID = 5, преодолев при этом 17 километров. Из пункта 5 можно отправиться в пункт 6 или 7. Так как до пункта 6 можно добраться, преодолев наименьшее количество километров (19 < 81), выбирается станция с ID = 6. От этой станции можно поехать либо на станцию с ID = 8, либо на станцию с ID = 7. Поскольку станция с ID = 8 отсутствует в списке, необходимо переместиться на станцию с ID = 7, преодолев 15 километров. От станции с ID = 7 передвигаемся на станцию с ID = 9, а затем на станцию с ID = 11. Итого между станциями было пройдено 17 + 19 + 15 + 40 + 13 километров.

Ответ к примеру: 104 11.

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

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

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

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

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

(А.Богданов) Транспортная компания владеет автомобилями с грузоподъемность M. Для транспортировки N грузов автомобили загружают предметами по убыванию веса, пока общая масса предметов не превышает грузоподъемность M. И далее процедуру повторяют для другого грузовика, до тех пор, пока все предметы не будут погружены. Нужно определить количество автомобилей для транспортировки всех предметов и общую загрузку предпоследнего автомобиля.

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

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

Пример:

6 100

30

10

40

50

10

20

В первый автомобиль возьмут 50+40+10, во второй 30+20+10

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

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

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

В первой строке даны два числа – количество товаров N и денежный лимит S. В каждой из следующих N строк через пробел указано 3 значения: номер товара, цена товара без скидки, категория товара с или без постфикса С.

Пример входных данных:

8 820
1 200 А
2 300 ВС
3 150 В
4 270 А
5 350 В
6 240 АС
7 200 ВС
8 300 АС

Товары с порядковыми номерами 2, 6, 7 и 8 подешевеют на 2, 6, 7 и 8 процентов соответственно, их новыми ценами станут суммы 294; 225,6; 186; 276. По условию задачи 1 покупается 4 товара с ценами 150, 186, 200, 225,6, при этом наибольшая возможная цена товара, приобретенного со скидкой, будет 276. Ответом для примера будет: 762 276.

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

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

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

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

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

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

6 4

40 36

32 30

30 14

21 21

17

14

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

При таких исходных данных условию задачи удовлетворяют набор коробок с длинами сторон 14, 21 и 30, т. е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 14.

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

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

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

Каждая строка входного файла содержит натуральное число и букву A или B. Число обозначает размер контейнера в условных единицах, буква – цвет этого контейнера (буквами A и B условно обозначены два цвета). В ответе запишите два целых числа: сначала максимально возможное количество контейнеров в одном блоке, затем минимальное количество ячеек для хранения всех контейнеров.

При перевозке труб для более компактной укладки решено перевозить трубы меньшего диаметра внутри труб большего диаметра. Для каждой трубы известен внешний диаметр D и толщина стенки S, выраженные в миллиметрах. Для предотвращения дефекта между трубами оставляют зазор в 3 миллиметра.

Несколько труб, вложенных одна в другую, называют пакетом.

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

Описание входных данных:

В первой строке приведено число N – количество труб. В каждой из следующих N строк приведены пары положительных целых чисел: внешний диаметр трубы D и толщина её стенки S.

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

5
100 5
80 3
74 4
62 5
60 3

При таких исходных данных можно собрать пакет из труб (100, 5), (80, 3), (62, 5). Следовательно, ответ будет
3 62

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

Известно количество страниц в каждой книге, которую необходимо разместить в шкафу.

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

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

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

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

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

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

5 75
10 1
15 1
25 0
20 0
15 0

Для указанных данных ответом будет пара чисел 3 20

(М. Ишимов) В городе живут N детей, которые ждут подарки на Новый Год. Снегурочка следит за поведением каждого из них на протяжении всего года. Каждый из ребят отправили письмо Деду Морозу, где написали, что они хотят получить в качестве подарка на Новый Год. Каждое письмо имеет свой номер, причём нечётные номера Снегурочка присвоила письмам от девочек, а чётные номера – письмам от мальчиков. Так как не все дети вели себя хорошо, в список писем от послушных детей Снегурочка записала только письма от M ребят (M < N). Известно, что подарки получат только те, кто попал в список Снегурочки. Определите количество мальчиков, которые вели себя хорошо на протяжении всего года, и количество девочек, которые не получат подарок на Новый Год.

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

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

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

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

8 5

25 48

17 13

16 25

13 93

48 16

39

93

18

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

При таких исходных данных условию задачи удовлетворяет набор мальчиков с номерами писем 48, 16, т.е. количество мальчиков, которые попали в список Снегурочки равно 2, и набор девочек с номерами писем 17, 39, т.е. количество девочек, которые не попали в список Снегурочки равно 2.

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