OpenFIPI 2.0
05BFA6
Задание выполняется с использованием прилагаемых файлов.
В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на D единиц меньше длины стороны другой коробки, при этом любые две соседние коробки сделаны из разных материалов. Известны длины сторон и материал коробок, имеющихся в наличии. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.
Входные данные
В первой строке входного файла находятся два натуральных числа через пробел: N (N < 100 000) – количество коробок и D (D < 10 000) – минимальная допустимая разность длин двух соседних коробок в «матрёшке». Каждая из следующих N строк содержит два разделённых пробелом натуральных числа, каждое из которых не превышает 10 000: длину стороны и условное обозначение вида материала коробки (0 или 1).
Запишите в ответе два числа: сначала наибольшее количество коробок, подходящих для упаковки подарка «матрёшкой», затем максимально возможную длину стороны самой маленькой коробки.
Типовой пример организации данных во входном файле
6 3
43 1
41 0
39 0
38 1
26 0
24 1
Пример входного файла приведён для шести коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.
При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 24, 39, 43 (материалы этих коробок – 1, 0, 1 соответственно) или 26, 38, 41 (материалы – 0, 1, 0 соответственно). Таким образом, количество коробок равно 3, а максимально возможная длина стороны самой маленькой коробки равна 26.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
