Chef would like go shopping to buy ingredients for his special dish. The local grocery store has some special discount offers. If you want to buy some set of ingredients you will pay for all ingredients except the cheapest one. Chef would like to spend as little money as possible. You have to help him. :)

The store is pretty small and stocks only one unit of each ingredients. Opposite each ingredient is a hanging price tag corresponding to it. The salesman walked away for a minute, giving Chef an opportunity to swap some price tags. He would like to swap some tags to minimize his purchase cost.

-----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 single integer N denoting the number of ingredients Chef needs to buy. The second line contains N space-separated integers A1, A2, ... , AN denoting the value  written on the price tags opposite the needed ingredients. The third line contains a single integer M denoting the number of special offers. The following M lines lists inventory of special offers, one offer per line. Each line contains an integer Ci followed by Ci integers denoting the indices of ingredients constituting the ith discount offer.

-----Output-----
For each test case, output a single line containing the minimal purchase cost.

-----Constraints-----
- T ≤ 5
- 1 ≤ N ≤ 15
- 1 ≤ Ai ≤ 106
- 0 ≤ M ≤ 2N-1
- 2 ≤ Ci ≤ N
- Subtask 1 (15 points):  1 ≤ N ≤  5
- Subtask 2 (25 points):  1 ≤ N ≤ 10
- Subtask 3 (60 points):  1 ≤ N ≤ 15

-----Example-----
Input:
1
4 
1 2 3 4
3
2 1 2
2 3 4
3 1 2 3

Output:
6

```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 = 'from itertools import permutations as p\ndef disc(a,b):\n for ai in a:\n  for bi in b:\n   if ai==bi:\n    return False\n return True\n\nfor i in range(eval(input())):\n n = eval(input())\n arr = list(map(int,input().split()))\n perms = list(p(arr))\n m = eval(input())\n offer = {}\n for i in range(m):\n  dup = list(map(int,input().split()))\n  try:\n   offer[dup[0]].append(dup[1:])\n  except:\n   offer[dup[0]] = [dup[1:]]\n ans = sum(arr)\n if n==1:\n  print(ans)\n elif n==2:\n  try:\n   if len(offer[2])>=1:\n    ans -= min(arr)\n  except:\n   pass\n  print(ans)\n elif n==3:\n  try:\n   if len(offer[3])>=1:\n    ans -= min(arr)\n  except:\n   pass\n  try:\n   if len(offer[2])>=1:\n    value = 9999999999\n    for item in perms:\n     cur = 0\n     cur += item[0]\n     cur += max(item[1],item[2])\n     if cur<value:\n      value = cur\n    if value<ans:\n     ans = value\n  except:\n   pass\n  print(ans)\n elif n==4:\n  try:\n   if len(offer[4])>=1:\n    ans -= min(arr)\n  except:\n   pass\n  #print ans\n  try:\n   if len(offer[3])>=1:\n    value = 9999999999\n    for item in perms:\n     cur = 0\n     cur = sum(item)\n     cur -= min(item[1],item[2],item[3])\n     if cur<value:\n      value = cur\n    if value<ans:\n     ans = value\n  except:\n   pass\n  #print ans\n  try:\n   if len(offer[2])>=1:\n    value = 9999999999\n    for item in perms:\n     cur = 0\n     cur = sum(item)\n     cur -= min(item[1],item[2])\n     if cur<value:\n      value = cur\n    if value<ans:\n     ans = value\n    #print ans\n   #print offer[2]\n   if len(offer[2])>=2:\n    flg = False\n    end = len(offer[2])\n    for i in range(end):\n     for j in range(i+1,end):\n      if disc(offer[2][i],offer[2][j]):\n       flg = True\n       break\n    #print flg\n    if flg:\n     value = 9999999999\n     for item in perms:\n      cur = 0\n      cur = sum(item)\n      cur -= min(item[1],item[0])\n      cur -= min(item[2],item[3])\n      if cur<value:\n       value = cur\n     if value<ans:\n      ans = value\n  except:\n   pass\n  print(ans)\n elif n==5:\n  try:\n   if len(offer[5])>=1:\n    ans -= min(arr)\n  except:\n   pass\n  try:\n   if len(offer[4])>=1:\n    value = 9999999999\n    for item in perms:\n     cur = 0\n     cur = sum(item)\n     cur -= min(item[1],item[2],item[3],item[4])\n     if cur<value:\n      value = cur\n    if value<ans:\n     ans = value\n  except:\n   pass\n  try:\n   if len(offer[2])>=1:\n    value = 9999999999\n    for item in perms:\n     cur = 0\n     cur = sum(item)\n     cur -= min(item[1],item[2])\n     if cur<value:\n      value = cur\n    if value<ans:\n     ans = value\n   if len(offer[2])>=2:\n    flg = False\n    end = len(offer[2])\n    for i in range(end):\n     for j in range(i+1,end):\n      if disc(offer[2][i],offer[2][j]):\n       flg = True\n       break\n    if flg:\n     value = 9999999999\n     for item in perms:\n      cur = 0\n      cur = sum(item)\n      cur -= min(item[1],item[0])\n      cur -= min(item[2],item[3])\n      if cur<value:\n       value = cur\n     if value<ans:\n      ans = value\n  except:\n   pass\n  try:\n   if len(offer[3])>=1:\n    value = 9999999999\n    for item in perms:\n     cur = 0\n     cur = sum(item)\n     cur -= min(item[1],item[2],item[3])\n     if cur<value:\n      value = cur\n    if value<ans:\n     ans = value\n  except:\n   pass\n  try:\n   if len(offer[3])>=1 and len(offer[2])>=1:\n    flg = False\n    for i in offer[3]:\n     for j in offer[2]:\n      if disc(i,j):\n       flg = True\n       break\n    if flg:\n     value = 9999999999\n     for item in perms:\n      cur = 0\n      cur = sum(item)\n      cur -= min(item[1],item[0])\n      cur -= min(item[2],item[3],item[4])\n      if cur<value:\n       value = cur\n     if value<ans:\n      ans = value\n  except:\n   pass\n  print(ans)\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 23017