SPSE - Space Shuttle Experiments

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 = {E1, E2, ..., Em} of instruments experiments and the commercial sponsor of Ej has agreed to pay NASA pj dollars for the results of the experiments.

The experiments use a set I = {I1, I2, ..., In} of instruments; each experiment Ej requires some of the instruments from the set. The cost of carrying instruments Ik is ck 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

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 ≤ 1000) and n (1 ≤ n ≤ 1000), where m denotes the number of experiments and n denotes the number of instruments. The next line contains m space separated integers, where the jth integer denotes the commercial sponsor of Ej paying NASA pj (1 ≤ pj ≤ 10000) dollars for the result of the experiment. The next line contains n space separated integers, where the kth integer denotes the cost of carrying the kth instrument, ck (1 ≤ ck ≤ 10000). Each of the next m lines contains an integer qi (1 ≤ qi ≤ n) followed by qi distinct integers each between 1 and n, separated by spaces. These qi integers denote the required instruments for the ith experiment.

Output

For each case, print the case number and the maximum revenue NASA can make using the experiments.

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

Sample Output
Case 1: 0
Case 2: 13

  • Người up: racer