{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"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 \u003d {E\u003csub\u003e1\u003c/sub\u003e, E\u003csub\u003e2\u003c/sub\u003e, ..., E\u003csub\u003em\u003c/sub\u003e}** of instruments experiments and the commercial sponsor of **E\u003csub\u003ej\u003c/sub\u003e** has agreed to pay NASA **p\u003csub\u003ej\u003c/sub\u003e** dollars for the results of the experiments.\n\nThe experiments use a set **I \u003d {I\u003csub\u003e1\u003c/sub\u003e, I\u003csub\u003e2\u003c/sub\u003e, ..., I\u003csub\u003en\u003c/sub\u003e}** of instruments; each experiment **E\u003csub\u003ej\u003c/sub\u003e** requires some of the instruments from the set. The cost of carrying instruments **I\u003csub\u003ek\u003c/sub\u003e** is **c\u003csub\u003ek\u003c/sub\u003e** dollars. And an instrument can be used for multiple experiments.\n\nThe professor\u0027s 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."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 100)**, denoting the number of test cases.\n\nEach case starts with a line containing two integers **m (1 \u0026le; m \u0026le; 100)** and **n (1 \u0026le; n \u0026le; 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\u003csup\u003eth\u003c/sup\u003e** integer denotes the commercial sponsor of **E\u003csub\u003ej\u003c/sub\u003e** paying NASA **p\u003csub\u003ej \u003c/sub\u003e(1 \u0026le; p\u003csub\u003ej\u003c/sub\u003e \u0026le; 10000)** dollars for the result of the experiment. The next line contains **n** space separated integers, where the **k\u003csup\u003eth\u003c/sup\u003e** integer denotes the cost of carrying the **k\u003csup\u003eth\u003c/sup\u003e** instrument, **c\u003csub\u003ek \u003c/sub\u003e(1 \u0026le; c\u003csub\u003ek\u003c/sub\u003e \u0026le; 10000)**. Each of the next **m** lines contains an integer **q\u003csub\u003ei\u003c/sub\u003e (1 \u0026le; q\u003csub\u003ei\u003c/sub\u003e \u0026le; n)** followed by **q\u003csub\u003ei\u003c/sub\u003e** distinct integers each between **1** and **n**, separated by spaces. These **q\u003csub\u003ei\u003c/sub\u003e** integers denote the required instruments for the **i\u003csup\u003eth\u003c/sup\u003e** experiment."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the maximum revenue NASA can make using the experiments."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 1\n10\n20\n1 1\n3 5\n20 30 40\n1 2 30 4 50\n3 1 2 3\n3 2 3 4\n1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 0\nCase 2: 13\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}