AMR11C  Robbing Gringotts
The Death Eaters are low on funds, and their leader Voldemort has asked them to get more money quickly, or face his wrath. They decide that the best way is to rob Gringotts Wizarding Bank.
By threatening one of the goblins in charge of the bank, the 'M' Death Eaters have discovered that Gringotts has 'N' vaults, with vault number 'i' containing X[i] gold items. The weights of the gold items in the ith vault are g[i][1],g[i][2],...,g[i][X[i]]. But as soon as a vault is robbed, the magical wards go off and alarm bells ring. Thus they have enough time to rob just one vault each, and all robberies have to take place at the same time. The Death Eaters have decided that no two of them will rob the same vault as this increases the chances of them being caught.
Death Eater j has a bag which can hold weight v[j]. They are a greedy and cowardly lot, so a Death Eater will only agree to rob a vault if he can fill up his bag completely to its capacity by taking some subset of the objects present in that vault. Note that it is not possible for a Death Eater to break any gold item; either it should be taken fully, or not be taken.
Find the maximum weight of gold they can take away by planning their strategy correctly.
Input (STDIN):
The first line contains the number of test cases T. T test cases follow. Each test case contains integers M and N on the first line. The next line contains M integers, the jth of which is v[j], which is the maximum weight of gold the jth Death Eater's bag can hold. The following N lines describe the gold items in the vaults. The ith line contains X[i], the number of gold items present in the ith vault, followed by X[i] integers g[i][1]..g[i][X[i]], denoting the weights of the each of the items present in the ith vault. There is a blank line after each test case.
Output (STDOUT):
Output one line for each test case, containing the maximum total weight of gold that the Death Eaters can rob.
Constraints:
1 <= T <= 10
1 <= N,M <= 50
1 <= X[i] <= 25
1 <= v[i],g[i][j] <= 10,000,000
Sample Input:
2
2 3
3 9
2 4 5
2 3 9
1 10
4 4
3 7 8 10
3 1 2 4
2 3 7
4 2 2 4 4
1 3
Sample Output:
12
28
hide comments
Dip:
20130114 20:30:33
On the best solution page of this problem, best time is 13.21 sec and here I see that the time limit is 10s. ???? 

foreverbell:
20130103 11:48:58
Note that the perfect matching of the left side may not exist. 

Buda IM (retired):
20120108 11:42:58
There is no way to pass the TL for worst case on spoj servers. TL is too strict 

[Rampage] Blue.Mary:
20111220 16:47:51
if he can fill up his bag ***completely*** 

Nikhil Garg:
20111219 16:06:25
Considering spoj servers, time limit is probably a little tight. 
Added by:  Varun Jalan 
Date:  20111215 
Time limit:  1.370s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Varun Jalan  ICPC Asia regionals, Amritapuri 2011 