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 Ci 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 Pj burles and get Qj meals - Aj, 1, Aj, 2, ..., Aj, 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 space-separated integers C1, C2, ..., CN denoting the costs of the meals, bought separately.
Each of the following M lines starts with a pair of integer numbers Pi and Qi, denoting the cost of the meal set and the number of meals in it, followed with the integer numbers Ai, 1 Ai, 2, ..., Ai, 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 ≤ Pi, Ci ≤ 106
- 1 ≤ M ≤ min{2N, 2 × 100000}
- No meal appears in the set twice or more times.
- Subtask 1 (16 points): 1 ≤ T ≤ 103, 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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "T = int(input())\nfor test_cases in range(T):\n [N,M] = list(map(int, input().split(' ')))\n cost_single = list(map(int, input().split(' ')))\n\n class meal(object):\n  def __init__(self,price,number,meal_list):\n   self.cost=price\n   self.num_meals=number\n   self.meals = [0]*N \n   for i in meal_list:\n    self.meals[i-1]=1\n   self.averageprice = price/number\n meal_sets = []\n for i in range(N):\n  meal_sets.append(meal(cost_single[i],1,[i+1]))\n for i in range(M):\n  line = input().split(' ')\n  if int(line[0])<sum(cost_single[j-1] for j in map(int, line[2:])): \n   meal_sets.append(meal(int(line[0]),int(line[1]),list(map(int, line[2:]))))\n M=len(meal_sets)-N\n meal_sets = sorted(meal_sets, key = lambda meal_sets:meal_sets.averageprice)\n\n min_cost=[0]\n min_cost[0]=sum(cost_single)\n\n def selection(choice,index):\n  this_cost=0;\n  for i in range(N+M):\n   this_cost+=choice[i]*meal_sets[i].cost\n  if this_cost>=min_cost[0]:\n   return 0\n  else:\n   temp_list=[]\n   check_list=[0]*N\n   for j in range(N+M):\n    if choice[j]==1:\n     temp_list.append(meal_sets[j].meals)\n   check=1 \n   if temp_list:\n    for j in range(N):  \n     check_list[j]=sum(row[j] for row in temp_list)\n     if check_list[j]==0:\n      check=0 \n      break\n    if check==1:\n     min_cost[0]=this_cost\n\n  if index==N+M-2:\n   selection(choice[0:index+1]+[0], index+1)\n   selection(choice[0:index+1]+[1], index+1)\n  elif index<N+M-1:\n   selection(choice[0:index+1]+[0]+choice[index+2:], index+1)\n   selection(choice[0:index+1]+[1]+choice[index+2:], index+1)\n\n\n selection([0]*(N+M),0)\n selection([1]+[0]*(N+M-1),0)\n\n print(min_cost[0])"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 16728