Bán lợn

Xem dạng PDF

Gửi bài giải

Điểm: 1,43 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
COI 02
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Mirko làm việc ở nông trại có ~M~ chuồng lợn, nhưng anh ta không có khóa để mở cửa chuồng lợn. Khách hàng lần lượt đến nông trại và họ có khóa một số chuồng lợn. Mỗi khách hàng đến, họ sẽ mở cửa mọi chuồng lợn mà họ có chìa khóa, và họ có thể mua một số lượng lợn nào đó trong các chuồng này.

Dữ liệu về khách hàng được gửi đến Mirko và buổi sáng, và Mirko muốn bán được nhiều lợn nhất. Sau khi bán một số lợn ở các chuồng này cho họ, Mirko có thể chuyển lợn còn lại giữa các chuồng đã mở. Mỗi chuồng chứa bao nhiêu lợn cũng được.

Xác định số lợn nhiều nhất có thể bán.

Input

Dòng đầu là hai số ~M~ và ~N~ ~\left(1 \leq M \leq 1000,\text{ }1 \leq N \leq 100\right)~ là số chuồng lợn và khách hàng.

Dòng tiếp theo ghi ~M~ số là số lợn trong mỗi chuồng ~\left(1,2,\ldots,M\right)~, số lợn thỏa mãn ~\geq 0~ và ~\leq 1000~.

~N~ dòng tiếp theo lưu thông tin về khách hàng và có dạng: ~A~ ~K_1~ ~K_2~ ~\ldots~ ~K_A~ ~B~. Nghĩa là anh ta có ~A~ cái khóa ~K_1,\ldots,K_A~ và muốn mua ~B~ lợn (các khóa sắp tăng dần). ~A, B~ có thể bằng ~0~.

Output

Số lợn nhiều nhất có thể bán.

Sample Input 1

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

Sample Output 1

7

Sample Input 2

6 6 
6 3 2 0 1 3 
2 1 2 0 
1 3 3 
1 1 1 
2 2 3 8 
2 4 5 2 
2 4 6 6

Sample Output 2

15

Sample Input 3

11 5 
1 2 2 1 0 2 4 1 1 1 2 
5 1 2 3 4 5 3 
4 1 2 6 7 5 
2 3 8 1 
3 3 6 11 5 
3 8 9 10 3

Sample Output 3

17

Bình luận

Hãy đọc nội quy trước khi bình luận.


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