Sắc Lệnh Giáo Dục

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Dolores Umbridge vừa được Bộ Phép Thuật bổ nhiệm làm Tổng Thanh tra Hogwarts. Bà ta lập tức ban hành hàng loạt Sắc Lệnh Giáo Dục nhằm kiểm soát mọi hoạt động trong trường.

Tại Hogwarts có $k$ loại hoạt động ngoại khóa, được đánh số từ $1$ đến $k$ . Có $n$ học sinh, mỗi học sinh tham gia một hoặc nhiều hoạt động và có một giá trị đóng góp $v_{i}$ cho trường (thể hiện tài năng, tinh thần, và sự cống hiến).

Dolores Umbridge sẽ cấm $k - d$ hoạt động (tức là chỉ cho phép $d$ hoạt động được tiếp tục). Một học sinh được coi là an toàn nếu ít nhất một hoạt động mà học sinh đó tham gia vẫn được phép. Nếu tất cả hoạt động của một học sinh đều bị cấm, học sinh đó sẽ bị đình chỉ và trường mất đi giá trị đóng góp tương ứng.

Giáo sư Dumbledore muốn tư vấn cho Hội đồng Trường chọn $d$ hoạt động được bảo vệ sao cho tổng giá trị đóng góp của các học sinh an toàn là lớn nhất.

Hãy giúp gíáo sư Dumbledore tìm tổng giá trị lớn nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $k$ , $d$ , $n$ - số loại hoạt động, số hoạt động được bảo vệ, và số học sinh.
$n$ dòng tiếp theo, mỗi dòng mô tả một học sinh: bắt đầu bằng số nguyên $c_{i}$ — số hoạt động mà học sinh tham gia, tiếp theo là $c_{i}$ số nguyên — danh sách các hoạt động, và cuối cùng là số nguyên $v_{i}$ - giá trị đóng góp.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng giá trị đóng góp lớn nhất có thể của các học sinh an toàn.

Ràng buộc

$1 \leq k \leq 20$
$1 \leq d \leq k$
$1 \leq n \leq 10^{5}$
$1 \leq c_{i} \leq k$
Mỗi hoạt động trong danh sách của một học sinh là duy nhất và nằm trong $[1, k]$
$1 \leq v_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 2 5 2 1 2 10 2 1 3 20 2 2 4 30 1 3 15 2 1 4 25	90	Chọn bảo vệ hoạt động $3$ và $4$ . Học sinh 2 (hoạt động 1,3, giá trị 20) an toàn nhờ hoạt động 3. Học sinh 3 (hoạt động 2,4, giá trị 30) an toàn nhờ hoạt động 4. Học sinh 4 (hoạt động 3, giá trị 15) an toàn nhờ hoạt động 3. Học sinh 5 (hoạt động 1,4, giá trị 25) an toàn nhờ hoạt động 4. Tổng = $20 + 30 + 15 + 25 = 90$ . Học sinh 1 (hoạt động 1,2) bị đình chỉ vì cả hai hoạt động đều bị cấm.
3 1 4 1 1 50 1 2 30 1 3 20 3 1 2 3 100	150	Chọn bảo vệ hoạt động $1$ . Học sinh 1 (giá trị 50) an toàn nhờ hoạt động 1. Học sinh 4 (giá trị 100) an toàn vì tham gia cả 3 hoạt động, trong đó có hoạt động 1. Tổng = $50 + 100 = 150$ .

Ghi chú

Ở ví dụ 1, nếu chọn bảo vệ hoạt động ${1, 2}$ thì các học sinh 1, 2, 3, 5 an toàn với tổng $10 + 20 + 30 + 25 = 85 < 90$ . Việc chọn ${3, 4}$ là tối ưu.

Ở ví dụ 2, bảo vệ hoạt động $2$ cho tổng $30 + 100 = 130$ , bảo vệ hoạt động $3$ cho tổng $20 + 100 = 120$ . Bảo vệ hoạt động $1$ cho kết quả tốt nhất.

Bình luận

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