import sys
'''
S(i) 表示开始工作时间小于等于i的雇佣员工的总数
需要满足的差分约束:
1. S(i) >= S(i-1) (i=1,2,3,4,....23)
2. S(0) >= 0
对于i >= 0 and i <= 8 而言
3. S(i) + S(23) - S(i+16) >= arr[i]
对于i >= 9 and i <= 23 而言
3. S(i) - S(i-8) >= arr[i]
4. S(i) - S(i-1) <= cnt[i], cnt[i]是从i时间开始工作的人的数量
从0到1000枚举S(23), 如果有一个S(23)能够让差分系统的最小解 小于等于 申请人的数量
就找到了一组可行解,找最小的S(23)即是答案
'''
from collections import Counter
from collections import deque
class SPFA:
# start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
# 包含节点为1, 2, 3, 4, ..... max_node_num
def __init__(self, start_node, edges, is_directed, max_node_num):
self.edges = edges[::]
self.start_node = start_node
self.is_directed = is_directed
self.max_node_num = max_node_num
# 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
def getMinPathLen(self):
return self.getInfo(min_path=True)
# 获取最长路径长度列表[(节点1,长度1), (节点2, 长度2) .....]
def getMaxPathLen(self):
return self.getInfo(min_path=False)
# min_path表示求的是最短路径还是最长路径
def getInfo(self, min_path = True):
link = {}
dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
dis[self.start_node] = 0
for a, b, w in self.edges:
if not self.is_directed:
# 无向图检查是否有负边
if (min_path == True and w < 0) and (min_path == False and w > 0):
# 有正环或者负环提前退出
return None
if a not in link:
link[a] = []
if b not in link:
link[b] = []
link[a].append((b, w))
link[b].append((a, w))
else:
if a not in link:
link[a] = []
link[a].append((b, w))
updated_nodes = deque()
updated_nodes.append(self.start_node)
in_que = [0] * (self.max_node_num + 1)
in_que[self.start_node] = 1
# 进行V次迭代,第V次检查是否是无解情况
iter_times = 0
while iter_times < self.max_node_num:
update_flag = False
# 利用上一轮迭代距离变小的点进行松弛操作
node_num = len(updated_nodes)
for _ in range(node_num):
a = updated_nodes.popleft()
in_que[a] = 0
if a not in link:
continue
for b, w in link[a]:
if dis[a] == 0x7fffffff:
if w == -0x7fffffff:
new_dis = 0
else:
new_dis = 0x7fffffff
elif dis[a] == -0x7fffffff:
if w == 0x7fffffff:
new_dis = 0
else:
new_dis = -0x7fffffff
else:
new_dis = dis[a] + w
if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
dis[b] = new_dis
update_flag = True
if in_que[b] == 0:
in_que[b] = 1
updated_nodes.append(b)
iter_times += 1
if iter_times == self.max_node_num:
if update_flag:
return None
if not update_flag:
break
return [[node, dis[node]] for node in range(1, self.max_node_num+1)]
t = int(input())
for _ in range(t):
arr = list( map(int, input().split()) )
n = int(input())
possible = [0] * 24
for i in range(n):
possible[int(input())] += 1
if sum(possible) == 0:
print(0)
else:
find_ans = False
min_cost = 0x7fffffff
for S23 in range(0, n+1):
# 为了方便计算,所有数值下标都往后移动了一个位置, 超级源点已定义为23, 实际存储时候用24的位置
edges = []
# S(i) >= S(i-1) (i=1,2,3,4,....22)
for i in range(1, 23):
edges.append((i-1+1, i+1, 0))
# S(22) <= S(23)
edges.append((24, 22+1, 0))
# S(i) >= S(i+16) - S23 + arr[i]
for i in range(8):
edges.append((i+16+1, i+1, arr[i]-S23))
# S(i) >= S(i-8) + arr[i]
for i in range(8, 23):
edges.append((i-8+1, i+1, arr[i]))
# S(23) - S(15) >= arr[23], S(15) <= S(23) - arr[23]
edges.append((15+1, 24, -(S23 - arr[23])))
# S(0) <= possible[0]
edges.append((0+1, 24, -possible[0]))
# S(i) - S(i-1) <= possible[i] i = 1, 2, 3..... 22
for i in range(1, 23):
edges.append((i+1, i-1+1, -possible[i]))
# S(23) - S(22) <= possible[23] => S(22) >= S(23) - possible[23]
edges.append((24, 22+1, S23 - possible[23]))
# 虚拟源点向所有点添加边 S(i) >= 0, i = 0, 1, 2, ..... 22
for i in range(23):
edges.append((24, i+1, 0))
algo = SPFA(24, edges, is_directed=True, max_node_num=24)
ans = algo.getMaxPathLen()
if ans is None:
continue
find_ans = True
min_cost = min(min_cost, S23)
if find_ans:
print(min_cost)
else:
print('No Solution')