Đàn Bò Robot

Bessie cần chế tạo $K$ con bò robot, mỗi con cần được lắp vi điều khiển tại $N$ vị trí khác nhau. Để phân biệt các con bò, không có hai con bò nào được có cùng bộ vi điều khiển: với mỗi cặp bò bất kỳ, phải tồn tại ít nhất một vị trí mà hai con bò đó sử dụng vi điều khiển khác model.

Tại vị trí $i$, có $M_i$ model vi điều khiển khác nhau, model thứ $j$ có giá $P_{i,j}$.

Hãy tìm cách chế tạo $K$ con bò robot với tổng chi phí nhỏ nhất, đảm bảo mọi con bò đều có bộ vi điều khiển phân biệt nhau.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
• $N$ dòng tiếp theo, dòng thứ $i$ bắt đầu bằng số nguyên $M_i$, theo sau là $M_i$ số nguyên $P_{i,1},P_{i,2},\dots ,P_{i,M_i}$.

Dữ liệu ra

Một số nguyên duy nhất — tổng chi phí nhỏ nhất để chế tạo $K$ con bò robot phân biệt.

Ràng buộc

• $1\le N\le 100000$
• $1\le K\le 100000$
• $1\le M_i\le 10$
• $1\le P_{i,j}\le {10}^8$
• Tổng số lượng model vi điều khiển trên tất cả các vị trí không vượt quá $500000$.
• Đảm bảo có ít nhất $K$ bộ vi điều khiển phân biệt.

Ví dụ

Ghi chú

Tổng số cấu hình phân biệt có thể là $4\times 3\times 5=60$, nhưng chỉ cần chọn 10 cấu hình rẻ nhất.

Con bò "cơ sở" (rẻ nhất) dùng model giá thấp nhất ở mỗi vị trí, chi phí $=1+2+1=4$. Mỗi con bò khác được tạo ra bằng cách nâng cấp một hoặc nhiều vị trí lên model đắt hơn.