Bài 2: Mua trà sữa (Tea.pas) (7 điểm) (1 giây)

Trà sữa bây giờ là một trong những thức uống phổ biến nhất ở Việt Nam. Ngày nay, đi bộ trên đường phố, bạn có thể tìm thấy một cửa hàng trà sữa ở khắp mọi nơi. Trà sữa thu hút sinh viên không chỉ là một thức uống ngon, mà còn với các loại phụ thêm được gọi là topping: alo vera, sôcôla flan, thạch dừa, bánh pudding trứng, trái cây ngọc trai, ... Ok, tôi sẽ ngừng viết câu này ở đây vì tôi phải lấy một ít trà sữa ngay lập tức. Nó thật là như chất gây nghiện.

Sau khi giảng dạy một lớp triết học cho sinh viên Việt Nam chuẩn bị cho kỳ thi Olympiad Triết học quốc tế, Dung mời sinh viên của mình thưởng thức một tách trà sữa. Người ta có bán các loại trà N và các loại thức ăn M. Mỗi loại trà hoặc mặt hàng có giá riêng. Đối với mỗi sinh viên, Dung sẽ mua cho người ấy một tách trà với đúng một loại topping. Chi phí của một cốc bằng với chi phí của trà cộng với chi phí của các topping. Tuy nhiên, không phải mọi loại topping đều có thể được trộn lẫn với mọi loại trà. Đối với mỗi loại trà, chúng ta biết danh sách các topping có thể được trộn cùng với nó.

Với số tiền mà Dung có, chị ta muốn biết có bao nhiêu sinh viên mà chị ta có thể mời tham dự bữa tiệc, nếu một sinh viên có đúng một ly trà sữa. Hãy nhớ rằng, chị ta không bao giờ nhìn sinh viên của mình uống trà sữa mà không uống bất cứ thứ gì, vì vậy chị ta phải tự mua cho mình một tách trà trước!

Trà sữa

Topping

Input: 

-          Dòng đầu tiên chứa một số nguyên N - số lượng các loại trà của cửa hàng.

-          Dòng thứ hai chứa N số nguyên - giá của tất cả các loại trà.

-          Dòng thứ ba chứa một số nguyên M - số lượng các chất kích thích mà cửa hàng có.

-          Dòng thứ 4 chứa M số nguyên - giá của tất cả các loại chất kích thích.

-          Lần thứ hai của N dòng tiếp theo mô tả các loại chất kích thích có thể trộn lẫn với loại trà thứ i. Dòng bắt đầu bằng một số nguyên K, K số tiếp theo là số nguyên . Tất cả các số nguyên j này nằm trong dải [1..M]. Mỗi số nguyên biểu thị một loại chất kích thích có thể được kết hợp với loại trà thứ i.

-          Dòng cuối cùng chứa một số nguyên X - số tiền mà Dung có.

Output: 

-          Viết số sinh viên tối đa mà Dung có thể mua trà sữa.

Hạn chế

Số tiền là từ 1 đến 10^9. Tất cả các số khác trong các tập tin đầu vào là từ 1 đến 1000.

Ví dụ:

Trong ví dụ này, có ba loại trà với giá 10, 20 và 30; cũng như năm loại mặt hàng với giá từ 1 đến 5.Làm rõ ví dụ:

Sự kết hợp rẻ nhất của chè và phần đầu là loại trà đầu tiên với loại bánh đứng thứ tư, với tổng chi phí là 14. Lưu ý rằng, trong khi kết hợp loại trà đầu tiên với loại đầu tiên thì giá sẽ thấp hơn (11) nhưng nó không được phép vì loại trà đầu tiên chỉ có thể kết hợp với các lớp 4 và 5 (Xem dòng 5 của đầu vào).

Do đó, với số tiền 42, Dung có thể mua ba chén trà, một cho anh ta và hai nữa cho sinh viên của mình!