1354 - Rubiks
Time Limit : 1 Second
Memory Limit : 64 MB
Submission: 452
Solved: 102
- Description
- Isun is a genius. Not only he is an expert in algorithm, but also he plays damn-good 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|白旗飘飘