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 i-th of them being the price of the i-th item in Karl's shopping cart. The third line contains M numbers, the i-th of them being the cash value of the i-th voucher Karl has in his wallet. M lines follow. Each line consists of a number Ki (the count of items such that you can pay for them using the i-th voucher, no more than 100) followed by Ki 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: 2018-08-21 10:26:26

Nice problem!

Before getting AC I got a bunch of TLE and RE, but learned a lot with this one.


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