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

Difficulty: interview

Starter code:

Solutions:
from itertools import permutations as p
def disc(a,b):
 for ai in a:
  for bi in b:
   if ai==bi:
    return False
 return True

for i in range(eval(input())):
 n = eval(input())
 arr = list(map(int,input().split()))
 perms = list(p(arr))
 m = eval(input())
 offer = {}
 for i in range(m):
  dup = list(map(int,input().split()))
  try:
   offer[dup[0]].append(dup[1:])
  except:
   offer[dup[0]] = [dup[1:]]
 ans = sum(arr)
 if n==1:
  print(ans)
 elif n==2:
  try:
   if len(offer[2])>=1:
    ans -= min(arr)
  except:
   pass
  print(ans)
 elif n==3:
  try:
   if len(offer[3])>=1:
    ans -= min(arr)
  except:
   pass
  try:
   if len(offer[2])>=1:
    value = 9999999999
    for item in perms:
     cur = 0
     cur += item[0]
     cur += max(item[1],item[2])
     if cur<value:
      value = cur
    if value<ans:
     ans = value
  except:
   pass
  print(ans)
 elif n==4:
  try:
   if len(offer[4])>=1:
    ans -= min(arr)
  except:
   pass
  #print ans
  try:
   if len(offer[3])>=1:
    value = 9999999999
    for item in perms:
     cur = 0
     cur = sum(item)
     cur -= min(item[1],item[2],item[3])
     if cur<value:
      value = cur
    if value<ans:
     ans = value
  except:
   pass
  #print ans
  try:
   if len(offer[2])>=1:
    value = 9999999999
    for item in perms:
     cur = 0
     cur = sum(item)
     cur -= min(item[1],item[2])
     if cur<value:
      value = cur
    if value<ans:
     ans = value
    #print ans
   #print offer[2]
   if len(offer[2])>=2:
    flg = False
    end = len(offer[2])
    for i in range(end):
     for j in range(i+1,end):
      if disc(offer[2][i],offer[2][j]):
       flg = True
       break
    #print flg
    if flg:
     value = 9999999999
     for item in perms:
      cur = 0
      cur = sum(item)
      cur -= min(item[1],item[0])
      cur -= min(item[2],item[3])
      if cur<value:
       value = cur
     if value<ans:
      ans = value
  except:
   pass
  print(ans)
 elif n==5:
  try:
   if len(offer[5])>=1:
    ans -= min(arr)
  except:
   pass
  try:
   if len(offer[4])>=1:
    value = 9999999999
    for item in perms:
     cur = 0
     cur = sum(item)
     cur -= min(item[1],item[2],item[3],item[4])
     if cur<value:
      value = cur
    if value<ans:
     ans = value
  except:
   pass
  try:
   if len(offer[2])>=1:
    value = 9999999999
    for item in perms:
     cur = 0
     cur = sum(item)
     cur -= min(item[1],item[2])
     if cur<value:
      value = cur
    if value<ans:
     ans = value
   if len(offer[2])>=2:
    flg = False
    end = len(offer[2])
    for i in range(end):
     for j in range(i+1,end):
      if disc(offer[2][i],offer[2][j]):
       flg = True
       break
    if flg:
     value = 9999999999
     for item in perms:
      cur = 0
      cur = sum(item)
      cur -= min(item[1],item[0])
      cur -= min(item[2],item[3])
      if cur<value:
       value = cur
     if value<ans:
      ans = value
  except:
   pass
  try:
   if len(offer[3])>=1:
    value = 9999999999
    for item in perms:
     cur = 0
     cur = sum(item)
     cur -= min(item[1],item[2],item[3])
     if cur<value:
      value = cur
    if value<ans:
     ans = value
  except:
   pass
  try:
   if len(offer[3])>=1 and len(offer[2])>=1:
    flg = False
    for i in offer[3]:
     for j in offer[2]:
      if disc(i,j):
       flg = True
       break
    if flg:
     value = 9999999999
     for item in perms:
      cur = 0
      cur = sum(item)
      cur -= min(item[1],item[0])
      cur -= min(item[2],item[3],item[4])
      if cur<value:
       value = cur
     if value<ans:
      ans = value
  except:
   pass
  print(ans)