Сердце страны
Нация Графия находится в состоянии войны. Соседние страны давно с завистью наблюдали, как Графия строила процветающие города и соединяла их сетью автомагистралей. Теперь они хотят получить свою долю.
Графия состоит из нескольких городов, связанных автомагистралями. Из-за сложного рельефа единственный способ перемещения между городами — это движение по автомагистралям. В каждом городе размещено определенное количество войск. Военное командование Графии знает, что для защиты любого города потребуется определенное количество войск, K. Они могут защищать город с помощью войск, размещенных в нем, а также войск из любого другого города, который напрямую соединен с ним автомагистралью, без промежуточных городов. Любые войска, находящиеся дальше, просто не успеют туда добраться вовремя. Они также знают, что их враги будут атаковать только один город за раз, так что войска в городе могут быть использованы для защиты этого города и любого из его соседей. Однако, если город не может быть защищен, то военное командование должно предположить, что войска, размещенные в этом городе, будут захвачены и не смогут помочь в защите Графии. В приведенном ниже случае, предположим, что K = 10. Город C может показаться хорошо защищенным, но в конечном итоге он падет.
Руководство Графии хочет определить Сердце своей страны — наибольшую возможную группу городов, которые могут взаимно защищать друг друга, даже если все остальные города падут.
Более формально, город защищаем, если он может собрать в общей сложности не менее K войск из себя и из городов, непосредственно прилегающих к нему. Набор городов защищаем, если каждый город в нем защищаем, используя только войска из себя и прилегающих городов в этом наборе. Сердце страны — это наибольший возможный защищаемый набор городов — то есть, никакой другой защищаемый набор городов не содержит больше городов.
Входные данные
Будет несколько наборов данных. Каждый набор начинается с двух целых чисел, N и K, где N — это количество городов (3 <= N <= 1000), а K — это количество войск, необходимых для защиты города.
Города пронумерованы от 0 до N-1.
На следующих N строках находятся описания городов, начиная с города 0. Каждая строка описания города начинается с целого числа T, указывающего количество войск, размещенных в этом городе (0 <= T <= 10000). За ним следует целое число M, указывающее количество автомагистралей, выходящих из этого города, и затем M целых чисел, указывающих города, в которые идут эти автомагистрали. Ни одна из автомагистралей не будет идти из одного и того же города в один и тот же город, так что каждый город в каждом списке будет уникальным. Ни одна автомагистраль не будет петлять из города обратно в тот же город. Автомагистрали двусторонние, так что если город I находится в списке города J, то гарантируется, что город J будет в списке города I во входных данных. Ввод заканчивается строкой с двумя разделенными пробелом 0.
Выходные данные
Для каждого набора данных выведите два целых числа в одной строке: количество городов в сердце страны и количество войск в сердце страны. Между числами должен быть пробел. Между выводами не должно быть пустых строк.