Бесси надеется обмануть Фермера Джона, построив стадо из \(K\)
(\(1 \leq K \leq 100,000\)) реалистичных робо-коров.
Но построить робо-корову - дело непростое.
Имеется \(N\) (\(1 \leq n \leq 100,000\)) индивидуальных позиций на роботе,
в которых должны размещаться микроконтроллеры. Один микроконтроллер
должен разместится в одном месте. Для каждого из этих мест Бесси может
выбрать микроконтроллер из различных моделей, которые отличаются по цене.
Для стада робо-коров, чтобы не вызвать подозрений у ФД. никакие два робота
не должны вести себя одинаково. Поэтому никакие два робота не должны иметь
совпадающие множества микроконтроллеров. То есть для люой пары роботов,
должно быть как минимум одно место, в котором два робота имеют различные
модели микроконтроллеров. Гарантируется, что всегда имеется достаточное
количество моделей микроконтроллеров, чтоыб можно было вполнить это условие.
Беси хочет сделать своё стадо как можно дешевле. Помогите ей определить
минимальную стоимость сделать это.
ФОРМАТ ВВОДА (файл roboherd.in):
Первая строка ввода содержит
\(N\) и
\(K\) разделённые одним пробелом.
Следующие \(N\) строк содержат описание различных микроконтроллеров
доступных для каждого месте. \(i\)-ая такая строка начинается с \(M_i\)
(\(1 \leq M_i \leq 10\)), определяющего количество моделей микроконтроллеров
доступных для места \(i\). Затем следуют \(M_i\) разделённых одиночными пробелами
целых чисел \(P_{i,j}\), определяющих стоимость этих моделей
(\(1 \le P_{i,j} \le 100,000,000\)).
ФОРМАТ ВЫВОДА (файл roboherd.out):
Выведите одну строку - минимальную стоимость сконструировать \(K\) роботов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6
|
61
|