HUST Monthly 2010.04.05
From: 20100405 12:00:00
To: 20100405 17:00:00
Now: 20170920 01:03:06
Status: Public
D  Rubiks
Time Limit: 1s
Memory Limit: 64MB
Submissions: 452 Solved: 102
 Description
 Isun is a genius. Not only he is an expert in algorithm, but also he plays damngood in many funny games. Besides, he can recover a Rubik in 16 seconds or even less. The man is very crazy about Rubiks, and he has bought a lot of Rubiks. As we know, there are so many kinds of Rubiks in the world. Isun wants to buy the most valuable ones with his limited money.
There are N kinds of Rubiks in all. Each of them has a price Pi(1<=i<=N) RMB and a value Vi(1<=i<=N). Isun will pay no more than M (RMB) in total.
In addition, there are some Rubik families like “甲X” or “封X”. And a kind of Rubik belongs to one family at most. If Isun buys a group of them, the value of them as a family will increase.
Can you get the largest value of the Rubiks that Isun can get with M (RMB). (Isun just buy one Rubik each kind at most)
 Input
 The input contains several test cases and is ended by EOF. Each test case begins with two integers: N (1<=N<=1000) and M (1<=M<=10000).
The second line contains N integers representing the prices of the Rubiks. (1<=Pi<=10000)
The third line contains N integers representing the value of the Rubiks. (1<=Vi<=10000)
Then a line contains an integer G(0<=G<=15) representing the number of the Rubik families.
Next G lines each with a start of an integer Si(1<=Si<=N) representing the number of Rubiks in the ith family. The following Si integers represent Rubik’s id (which start from 1 to N). And an integer Yi at the end means the value increased if you buy them all.(1<=Yi<=10000)
 Output
 There should be one line per test case containing the largest value.
 Sample Input

4 10
4 5 3 6
1 2 100 200
1
2 1 2 330
 Sample Output

333
 Hint
 Isun will buy Rubik 1 and Rubik 2, which make up family 1 and get 330 value increased. So they value 333 in all which is the largest value Isun can get with 10 RMB.
 Source
 Hust Monthly 10.04.05/Baiqi2piao白旗飘飘