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: UNKNOWN_DIFFICULTY

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
		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[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
		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)