Роботизоване стадо корів
Бессі планує обдурити Фермера Джона, створивши стадо з 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 роботів.