Задача #486

(А. Рогов) Строительная организация возводит два высотных здания, находящихся на расстоянии 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.

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