There are n experiments can be done in the space. We can gain Pi dollars income if the i-th experiment is chosen to be processed in the space. But for each experiment, it needs some device among a total of m devices numbered 1 to m to process. It costs Cj dollars to buy and set up j-th device. So, what is the largest possible net income? Here the net income stands for the summation of chosen experiments’ income subtract all the used devices’ cost.
There are multiple test cases in the input file. For each test case, first line contains two integers n, m (1<= n, m <=500). The second line contains n integers P1, P2, …, Pn. The third line contains m integers C1, C2, …, Cm. (1 <= Pi, Cj <= 1,000,000) Next n lines each line is in the form
ki Ai1 Ai2 … Aiki
Where ki denotes the number of devices (0 <= ki <= m) used in i-th experiment and each Aij denotes the device's number.
n = m = 0 terminates the input, don't proceed it.
For each test case, please output the largest net income in a line.
4 4 2 5 6 13 3 4 6 8 2 1 2 2 2 3 2 3 4 1 4 0 0
6
Migrated from old NTUJ.
算法藝術 P.317
| No. | Testdata Range | Score |
|---|