Đàn Bò Robot

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 100 000$
$1 \leq K \leq 100 000$
$1 \leq M_{i} \leq 10$
$1 \leq P_{i, j} \leq 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á $500 000$ .
Đảm bảo có ít nhất $K$ bộ vi điều khiển phân biệt.

Ví dụ

Input	Output	Giải thích
3 10 4 1 5 3 10 3 2 3 3 5 1 3 4 6 6	61	Có 3 vị trí: vị trí 1 có 4 model (giá 1, 3, 5, 10), vị trí 2 có 3 model (giá 2, 3, 3), vị trí 3 có 5 model (giá 1, 3, 4, 6, 6). Con bò rẻ nhất dùng model giá thấp nhất mỗi vị trí: 1+2+1=4. Cần chế tạo 10 con bò với tổng chi phí nhỏ nhất là 61.

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.

Bình luận

Không có bình luận tại thời điểm này.