Задание 26 ЕГЭ по информатике

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

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

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

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

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

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

6 4

40 36

32 30

30 14

21 21

17

14

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

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

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/5643_26.txt