SHOP2  Shopping II
Karl is going to spend his holiday in Nothingland. Since there is nothing there, he has to buy all supplies now. At the moment, he is waiting at the checkout counter with a shopping cart full of stuff.
Of course, he has a sufficient amount of money in his wallet. However, he prefers to use alternate means of payment if possible: luncheon vouchers, gift certificates, different types of coupons, etc. What makes the matter complicated is that the use of these items is often limited: e.g., luncheon vouchers can only be used to buy food, and gift certificates are often limited to a certain type of gifts.
Problem specification
You are given the number N(1<= N <=2000) of items in Karl's shopping cart and their prices. You are also given the number M(1<= M <=2000) of vouchers in his wallet, together with the information on their allowed use.
When paying for his shopping, Karl may use vouchers for a larger sum than the cost of the things he is buying. It is also possible to split an item's cost between multiple vouchers and use a voucher to pay for more than one item.
Compute the minimum amount of additional cash money Karl needs to pay for his shopping.
Input specification
The first line of input file contains an integer T specifying the number of test cases. T blocks follows, each block describes one test case. Each block is preceded by a blank line.
Each block starts with line containing two positive integers N (the number of items) and M (the number of vouchers). The second line contains N numbers(each no more than 10000), the ith of them being the price of the ith item in Karl's shopping cart. The third line contains M numbers, the ith of them being the cash value of the ith voucher Karl has in his wallet. M lines follow. Each line consists of a number K_{i} (the count of items such that you can pay for them using the ith voucher, no more than 100) followed by K_{i} numbers (the numbers of those items; items are numbered from 1 to N).
Output specification
For each test case output a single number specifying how much cash money Karl needs to pay for his shopping.
Example
Input: 1 3 2 15 20 10 20 30 3 1 2 3 1 3
Output: 15
hide comments
joqsan_77:
20180821 10:26:26
Nice problem!

Added by:  Fudan University Problem Setters 
Date:  20090531 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  IPSC 2009 