Задача #2568

(Л. Шастин) В одном популярном городе-курорте нашей замечательной страны ведутся срочные работы по укреплению опоры местного автомобильного моста, связывающего разные части города. Для увеличения плотности основного каркаса используют разноразмерные железобетонные балки, из которых по двум сторонам скрепляются и прокладываются платформы длиной $R$ условных единиц. Завод-производитель сварочных изделий предлагает к приобретению $N$ балок, пронумерованных от $1$ до $N$, каждая из которых может быть доступна в нескольких размерах, но продается исключительно в одном экземпляре. В целях экономии государственного бюджета администрация города закупает наименьшее количество балок, суммарной длины которых достаточно для построения вышеописанных платформ.

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

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

В первой строке входного файла находятся два числа: $N$ (натуральное число, не превышающее 10⁵) — количество балок, доступных для покупки, и $R$ (натуральное число, не превышающее 10¹⁰) — длина одной платформы (в у.е). В каждой из следующих $N$ строк находятся размеры соответствующей балки, разделенные друг от друга одним пробелом. Каждая балка может иметь разное количество размеров (от 1 до 15). Все размеры представлены натуральными числами, не превышающими 10⁷. Информация о каждой балке записана на отдельной строке.

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

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

5 63
20 15 30
10 5 14 9 11
40 8
7
50 7 12 9 16 35

Пример входного файла приведён для набора из 5 балок. При таких исходных данных для построения платформ нужной длины по двум сторонам можно купить балку №1 в размере 30 у.е., балку №3 в размере 40 у.е, балку №5 в размере 50 у.е. и напоследок любую балку из доступных, но наименьший подходящий размер в 7 у.е. будет иметь балка №4. Ответ: 4 4.