Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mtele

TV muốn chiếu một trận bóng đá. Hệ thống mạng của họ gồm một số bộ truyền dẫn, khuyếch đại và người dùng ; hệ thống này có thể mô tả bằng một cây. Gốc của cây là bộ phát tín hiệu về trận bóng, nút lá là người xem và các nút khác là bộ truyền dẫn/ Biết chi phí của việc truyền tín hiện từ bộ truyền dẫn tới người dùng, hoặc tới bộ truyền dẫn khác, thì chi phí của việc phát sóng là tổng chi phí của các truyền dẫn được sử dụng. Mỗi người dùng trả một số tiền để xem bóng đá và nhà đài quyết định xem có cung cấp cho họ tín hiệu không (vì trả bèo quá). Tính số lượng người xem bóng đá tối đa mà nhà đài không mất tiền do việc truyền trận bóng.

Input

Dòng đầu là hai số N, M, 2 ≤ N ≤ 3000,1 ≤ M ≤ N-1, the số đỉnh của cây và số người xem. Gốc cây đánh số là 1, bộ truyền dẫn từ 2-> N-M và người dùng từ N-M+1 tới N. N-M dòng tiếp theo lưu thông tin của mỗi bộ truyền dẫn, có dạng:

K A1 C1 A2 C2 ... AK CK

Bộ truyền dẫn này truyền tín hiệu tới K bộ truyền dẫn/ người dùng khác, mỗi thông tin được xác định bởi cặp Ai, CI; Ai - mã số người dùng hoặc bộ truyền dẫn khác và Ci - chi phi của việc truyền tín hiệu từ bộ truyền dẫn hiện tại tới đó. Dòng cuối cùng gồm M số, chi phí mà người dùng muốn trả để xem bóng đá.

Output

Số người xem bóng đá tối đa thỏa yêu cầu đề bài.

Sample

Input:
5 3
2 2 2 5 3
2 3 2 4 3
3 4 2

Output:
2

Input:
5 3
2 2 2 5 3
2 3 2 4 3
4 4 2

Output:
3

Input:
9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

Output:
5