Bessie hy vọng đánh lừa Farmer John bằng cách chế tạo một đàn gồm \(K\) con bò robot trông như thật (\(1 \leq K \leq 100\,000\)).

Hóa ra việc chế tạo một con bò robot khá phức tạp. Trên robot có \(N\) vị trí riêng biệt (\(1 \leq N \leq 100\,000\)) cần được kết nối với vi điều khiển (tức là phải kết nối đúng một vi điều khiển tại mỗi vị trí). Với mỗi vị trí này, Bessie có thể chọn một trong nhiều mẫu vi điều khiển khác nhau, mỗi mẫu có chi phí tương ứng.

Để đàn bò robot trông thuyết phục với Farmer John, không có hai robot nào được hành xử giống hệt nhau. Vì vậy, không có hai robot nào được có chính xác cùng một bộ vi điều khiển. Với bất kỳ cặp robot nào, phải có ít nhất một vị trí mà hai robot sử dụng hai mẫu vi điều khiển khác nhau. Đảm bảo rằng luôn có đủ các mẫu vi điều khiển khác nhau để thỏa mãn ràng buộc này.

Bessie muốn chế tạo đàn bò robot với chi phí thấp nhất có thể. Hãy giúp cô xác định chi phí nhỏ nhất để làm được điều đó!

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\), cách nhau bởi một dấu cách.

\(N\) dòng tiếp theo mô tả các mẫu vi điều khiển khác nhau có sẵn cho từng vị trí. Dòng thứ \(i\) trong số này bắt đầu bằng \(M_i\) (\(1 \leq M_i \leq 10\)), là số mẫu có sẵn cho vị trí \(i\). Tiếp theo là \(M_i\) số nguyên cách nhau bởi dấu cách \(P_{i,j}\), biểu thị chi phí của các mẫu này (\(1 \leq P_{i,j} \leq 100\,000\,000\)).

Dữ liệu ra

In một dòng chứa chi phí nhỏ nhất để chế tạo \(K\) robot.

Ví dụ

3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6

61

Nguồn

USACO 2016 December Contest, Platinum — Robotic Cow Herd. Tác giả đề: Richard Peng và Nathan Pinsker.

https://usaco.org/index.php?page=viewproblem2&cpid=674