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

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\le k\le 20$
• $1\le d\le k$
• $1\le n\le {10}^5$
• $1\le c_i\le 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\le v_i\le {10}^9$

Ví dụ