FastFood Combos

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Sometimes Sergey visits fast food restaurants. Today he is going to visit the one called PizzaKing.
Sergey wants to buy N meals, which he had enumerated by integers from 1 to N. He knows that the meal i costs C_{i} rubles. He also knows that there are M meal sets in the restaurant.
The meal set is basically a set of meals, where you pay P_{j} burles and get Q_{j} meals  A_{j, 1}, A_{j, 2}, ..., A_{j, Qj}.
Sergey has noticed that sometimes he can save money by buying the meals in the meal sets instead of buying each one separately. And now he is curious about what is the smallest amount of rubles he needs to spend to have at least one portion of each of the meals.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a pair of integer numbers N and M denoting the number of meals and the number of the meal sets.
The second line contains N spaceseparated integers C_{1}, C_{2}, ..., C_{N} denoting the costs of the meals, bought separately.
Each of the following M lines starts with a pair of integer numbers P_{i} and Q_{i}, denoting the cost of the meal set and the number of meals in it, followed with the integer numbers A_{i, 1} A_{i, 2}, ..., A_{i, Qi} denoting the meal numbers.
Output
For each test case, output a single line containing the minimal total amount of money Sergey needs to spend in order to have at least one portion of each meal.
Constraints
 1 ≤ P_{i}, C_{i} ≤ 10^{6}
 1 ≤ M ≤ min{2^{N}, 2 × 100000}
 No meal appears in the set twice or more times.
 Subtask 1 (16 points): 1 ≤ T ≤ 10^{3}, 1 ≤ N ≤ 8
 Subtask 2 (23 points): For each test file, either 1 ≤ T ≤ 10, 1 ≤ N ≤ 12 or the constraints for Subtask 1 are held.
 Subtask 3 (61 points): For each test file, either T = 1, 1 ≤ N ≤ 18 or the constraints for Subtask 1 or 2 are held.
Example
Input: 1 3 3 3 5 6 11 3 1 2 3 5 2 1 2 5 2 1 3 Output: 10
Explanation
Example case 1. If Sergey buys all the meals separately, it would cost him 3 + 5 + 6 = 14 rubles. He can buy all of them at once by buying the first meal set, which costs for 11 rubles, but the optimal strategy would be either to buy the second and the third meal set, thus, paying 5 + 5 = 10 rubles, or to buy the third meal set and the second meal separately by paying the same amount of 10 rubles.
Author:  xcwgf666 
Tester:  mgch 
Editorial  http://discuss.codechef.com/problems/FFCOMB 
Tags  bits, dynamicprogramming, ltime41, xcwgf666 
Date Added:  5102016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions