Một mạng truyền hình cáp có thu phí đang lên kế hoạch phát sóng một trận bóng đá quan trọng. Mạng truyền hình này gồm hệ thống các trạm truyền tín hiệu và các thiết bị đầu cuối của người dùng, được tổ chức dưới dạng một cấu trúc cây. Gốc của cây là địa điểm diễn ra trận đấu, các lá là các thiết bị đầu cuối của người dùng, các nút trung gian là các trạm phát lại tín hiệu.

Chi phí truyền tín hiệu từ một trạm đến các trạm khác hoặc đến người dùng đều đã biết. Chi phí tổng cộng của một lần phát sóng là tổng chi phí truyền tín hiệu đến tất cả các người dùng được phục vụ.

Mỗi người dùng sẵn sàng chi trả một khoản tiền để xem trận đấu. Mạng truyền hình có quyền lựa chọn cung cấp hoặc không cung cấp tín hiệu cho một số người dùng.

Yêu cầu

• Viết chương trình tìm một phương án sao cho:
• Mạng truyền hình không bị lỗ (tổng chi phí không vượt quá tổng số tiền thu được từ người dùng).
• Số lượng người dùng được phục vụ là nhiều nhất.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên \(N\) và \(M\):
• \(N\) (\(2 \le N \le 3000\)) - tổng số nút trong mạng.
• \(M\) (\(1 \le M \le N-1\)) - số người dùng cuối (thiết bị đầu cuối).
• Gốc của cây là nút số \(1\) (trạm trực tiếp tại hiện trường).
• Các nút từ \(2\) đến \(N-M\) là các trạm trung gian.
• Các nút từ \(N-M+1\) đến \(N\) là các thiết bị đầu cuối của người dùng.
• Dòng thứ \(i+1\) (\(1 \le i \le N-M\)) mô tả các nút con của nút \(i\), có dạng: \[ K \ A_1\ C_1\ A_2\ C_2\ \dots\ A_K\ C_K \] Trong đó:
• \(K\) - số lượng nút con,
• Mỗi cặp \(A_j\ C_j\) thể hiện: từ nút \(i\) đến nút \(A_j\) tốn chi phí \(C_j\) (đơn vị: chi phí truyền tín hiệu).
• Dòng cuối cùng gồm \(M\) số nguyên, mỗi số là số tiền mà người dùng (các nút từ \(N-M+1\) đến \(N\)) sẵn sàng chi trả để xem trận đấu.

Tất cả chi phí và số tiền đều là số nguyên không quá \(10\).

Dữ liệu ra

• In ra một dòng duy nhất là số người dùng tối đa có thể được phục vụ mà không làm mạng truyền hình bị lỗ.

Input 1

5 3
2 2 2 5 3
2 3 2 4 3
3 4 2

Output 1

2

Giải thích ví dụ

• Tổng số nút: 5 - gồm 2 trạm (1 và 2), và 3 người dùng (3, 4, 5).
• Các kết nối:
• Từ trạm 1 đến trạm 2: chi phí 2.
• Từ trạm 1 đến người dùng 5: chi phí 3.
• Từ trạm 2 đến người dùng 3: chi phí 2.
• Từ trạm 2 đến người dùng 4: chi phí 3.
• Các người dùng sẵn sàng chi trả: người dùng 3 trả 3, 4 trả 4, 5 trả 2.
• Nếu phục vụ cả 3 người dùng:
• Chi phí: \(2 + 3 + 2 + 3 = 10\)
• Thu nhập: \(3 + 4 + 2 = 9\)
• Bị lỗ \(\Rightarrow\) không hợp lệ.
• Nếu chỉ phục vụ người dùng 3 và 4:
• Chi phí: \(2 + 2 + 3 = 7\)
• Thu nhập: \(3 + 4 = 7\)
• Hòa vốn \(\Rightarrow\) hợp lệ.
• Kết luận: có thể phục vụ tối đa 2 người dùng.

Input 2

6 3
2 2 8 6 1
2 3 4 4 2
1 5 7
6 10 7

Output 2

3