Роботизированное стадо коров
Бесси надеется обмануть Фермера Джона, построив стадо из k реалистичных робо-коров.
Но построить робо-корову - дело непростое. Имеется n индивидуальных позиций на роботе, в которых должны размещаться микроконтроллеры. Один микроконтроллер должен разместится в одном месте. Для каждого из этих мест Бесси может выбрать микроконтроллер из различных моделей, которые отличаются по цене.
Для стада робо-коров, чтобы не вызвать подозрений у ФД. никакие два робота не должны вести себя одинаково. Поэтому никакие два робота не должны иметь совпадающие множества микроконтроллеров. То есть для люой пары роботов, должно быть как минимум одно место, в котором два робота имеют различные модели микроконтроллеров. Гарантируется, что всегда имеется достаточное количество моделей микроконтроллеров, чтоыб можно было вполнить это условие.
Беси хочет сделать своё стадо как можно дешевле. Помогите ей определить минимальную стоимость сделать это.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 10^5) и k (1 ≤ k ≤ 10^5).
Следующие n строк содержат описание различных микроконтроллеров доступных для каждого месте. i-ая такая строка начинается с m[i] (1 ≤ m[i] ≤ 10), определяющего количество моделей микроконтроллеров доступных для места i. Затем следуют m[i] разделённых одиночными пробелами целых чисел P[i,j] (1 ≤ P[i,j] ≤ 10^8), определяющих стоимость этих моделей.
Выходные данные
Выведите одну строку - минимальную стоимость сконструировать k роботов.