Time Limit: 2 second(s) | Memory Limit: 32 MB |
Professor Spook is consulting for NASA, which is planning a series of space shuttle flights and must decide which commercial experiments to perform and which instruments to have on board each flight. For each flight NASA considers a set E = {E_{1}, E_{2}, ..., E_{m}} of instruments experiments and the commercial sponsor of E_{j} has agreed to pay NASA p_{j} dollars for the results of the experiments.
The experiments use a set I = {I_{1}, I_{2}, ..., I_{n}} of instruments; each experiment E_{j} requires some of the instruments from the set. The cost of carrying instruments I_{k} is c_{k} dollars. And an instrument can be used for multiple experiments.
The professor's job is to determine which experiments to perform and which instruments to carry for a given flight in order to maximize the net revenue, which is the total income from the experiments performed minus the total cost of the instruments carried. Since he is not a programmer, he asked your help.
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing two integers m (1 ≤ m ≤ 100) and n (1 ≤ n ≤ 100), where m denotes the number of experiments and n denotes the number of instruments. The next line contains m space separated integers, where the j^{th} integer denotes the commercial sponsor of E_{j} paying NASA p_{j }(1 ≤ p_{j} ≤ 10000) dollars for the result of the experiment. The next line contains n space separated integers, where the k^{th} integer denotes the cost of carrying the k^{th} instrument, c_{k }(1 ≤ c_{k} ≤ 10000). Each of the next m lines contains an integer q_{i} (1 ≤ q_{i} ≤ n) followed by q_{i} distinct integers each between 1 and n, separated by spaces. These q_{i} integers denote the required instruments for the i^{th} experiment.
For each case, print the case number and the maximum revenue NASA can make using the experiments.
Sample Input |
Output for Sample Input |
2 1 1 10 20 1 1 3 5 20 30 40 1 2 30 4 50 3 1 2 3 3 2 3 4 1 5 |
Case 1: 0 Case 2: 13 |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |