Chef is operating a slush machine. The machine produces slush drinks with $M$ flavors (numbered $1$ through $M$); for each valid $i$, the maximum number of drinks with flavour $i$ the machine can produce is $C_i$.
Chef expects $N$ customers to come buy slush drinks today. The customers are numbered $1$ through $N$ in the order in which they buy the drinks. For each valid $i$, the favorite flavour of the $i$-th customer is $D_i$ and this customer is willing to pay $F_i$ units of money for a drink with this flavour, or $B_i$ units of money for a drink with any other flavuor. Whenever a customer wants to buy a drink:
- if it is possible to sell this customer a drink with their favourite flavour, Chef must sell them a drink with this flavour
- otherwise, Chef must sell this customer a drink, but he may choose its flavour
Chef wants to make the maximum possible profit. He is asking you to help him decide the flavours of the drinks he should sell to the customers in order to maximise the profit.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $M$.
- The second line contains $M$ space-separated integers $C_1, C_2, \ldots, C_M$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains three space-separated integers $D_i$, $F_i$ and $B_i$.

-----Output-----
For each test case, print two lines:
- The first of these lines should contain a single integer — the maximum profit.
- The second line should contain $N$ space-separated integers denoting the flavours of the drinks Chef should sell, in this order.
If there are multiple solutions, you may find any one.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N, M \le 10^5$
- $1 \le D_i \le M$ for each valid $i$
- $1 \le C_i \le N$ for each valid $i$
- $1 \le B_i < F_i \le 10^9$ for each valid $i$
- $C_1+C_2+\ldots+C_M \ge N$
- the sum of $N$ over all test cases does not exceed $10^6$
- the sum of $M$ over all test cases does not exceed $10^6$

-----Example Input-----
1
5 3
1 2 3
2 6 3
2 10 7
2 50 3
1 10 5
1 7 4

-----Example Output-----
33
2 2 3 1 3

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = 0
	s1 = 0
	ans = []
	j = 0
	q = []
	q1 = []
	p = list(map(int, input().split()))
	for i in p:
		s += i
	if s >= n:
		while n:
			(d, f, b) = map(int, input().split())
			if p[d - 1] > 0:
				s1 += f
				p[d - 1] -= 1
				j += 1
				ans.append(d)
			else:
				s1 += b
				ans.append(0)
				q.append(j)
				j += 1
			n -= 1
		for i in range(len(p)):
			if p[i] != 0:
				q1.append([i, p[i]])
		x = 0
		for i in q:
			if q1[x][1] != 0:
				ans[i] = q1[x][0] + 1
				q1[x][1] -= 1
			else:
				x += 1
				ans[i] = q1[x][0] + 1
				q1[x][1] -= 1
	print(s1)
	print(*ans)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	d = {}
	for i in range(len(c)):
		d[i + 1] = c[i]
	ans = []
	profit = 0
	r_1 = 0
	for i in range(n):
		(t_1, t_2, t_3) = list(map(int, input().split()))
		if d[t_1] > 0:
			profit += t_2
			d[t_1] -= 1
			ans.append(t_1)
		else:
			profit += t_3
			r_1 += 1
			ans.append('')
	print(profit)
	rem = []
	for i in d:
		if d[i] > 0:
			rem += [i] * d[i]
			d[i] = 0
		if len(rem) >= r_1:
			break
	j = 0
	for i in range(len(ans)):
		if ans[i] == '':
			ans[i] = rem[j]
			j += 1
	print(*ans)


for t in range(int(input())):
	(n, m) = [int(j) for j in input().split()]
	c = [int(j) for j in input().split()]
	demand_supply = dict()
	for i in range(m):
		demand_supply[i] = -1 * c[i]
	flav = []
	F = []
	B = []
	for i in range(n):
		(d, f, b) = [int(j) for j in input().split()]
		F.append(f)
		B.append(b)
		flav.append(d - 1)
	ans = 0
	l = []
	flag = []
	for i in range(n):
		if c[flav[i]] > 0:
			l.append(flav[i])
			ans += F[i]
			c[flav[i]] -= 1
		else:
			l.append(0)
			ans += B[i]
			flag.append(i)
	ct = 0
	for i in c:
		while i > 0 and flag:
			l[flag[0]] = ct
			i -= 1
			flag = flag[1:]
		ct += 1
	print(ans)
	for i in l:
		print(i + 1, end=' ')
	print()


def solve(quantity, N, M):
	(ans, drink) = (0, [-1] * N)
	for i in range(N):
		(D, F, B) = map(int, input().split())
		if quantity[D - 1] > 0:
			ans += F
			drink[i] = D
			quantity[D - 1] -= 1
		else:
			ans += B
	index = 0
	for i in range(N):
		if drink[i] != -1:
			continue
		while quantity[index] == 0:
			index += 1
		drink[i] = index + 1
		quantity[index] -= 1
	print(ans)
	for i in drink:
		print(i, end=' ')
	print()
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	quantity = list(map(int, input().split()))
	solve(quantity, N, M)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	drink_freq = list(map(int, input().split()))
	orders = []
	ans = []
	money = 0
	for i in range(n):
		(d, f, b) = map(int, input().split())
		orders.append((d, f, b))
	for j in range(n):
		if drink_freq[orders[j][0] - 1] != 0:
			money += orders[j][1]
			drink_freq[orders[j][0] - 1] -= 1
			ans.append(orders[j][0])
		else:
			money += orders[j][2]
			ans.append(-1)
	print(money)
	y = []
	for l in range(len(drink_freq)):
		if drink_freq[l] != 0:
			y.append([l, drink_freq[l]])
	ref = 0
	for k in range(n):
		if ans[k] == -1:
			if y[ref][1] != 0:
				ans[k] = y[ref][0] + 1
				y[ref][1] -= 1
			else:
				ref += 1
				ans[k] = y[ref][0] + 1
				y[ref][1] -= 1
	print(*ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	l = []
	k = [0 for _ in range(n)]
	max_pro = 0
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] > 0:
			c[d - 1] -= 1
			k[i] = d
			max_pro += f
		else:
			l.append((d, b, i))
	(v, j) = (0, 0)
	while j < len(l):
		if c[v] == 0:
			v = v + 1
		else:
			(d, b, i) = l[j]
			k[i] = v + 1
			max_pro += b
			c[v] -= 1
			j = j + 1
	print(max_pro)
	print(*k)


import sys
import bisect
import math
from collections import defaultdict
from collections import deque
from collections import Counter
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(var)

def l():
	return list(map(int, data().split()))

def sl():
	return list(map(str, data().split()))

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [[val for i in range(n)] for j in range(m)]
for _ in range(int(data())):
	(n, m) = sp()
	arr = l()
	(d, f, b) = (list(), list(), list())
	for i in range(n):
		(a, e, c) = sp()
		d.append(a)
		f.append(e)
		b.append(c)
		d[i] -= 1
	answer = [0 for i in range(n)]
	profit = 0
	for i in range(n):
		answer[i] = 0
		if arr[d[i]]:
			arr[d[i]] -= 1
			answer[i] = 1
			profit += f[i]
		else:
			profit += b[i]
	j = 0
	out(str(profit) + '\n')
	for i in range(n):
		if answer[i]:
			out(str(d[i] + 1) + ' ')
			continue
		while not arr[j]:
			j += 1
		out(str(j + 1) + ' ')
		arr[j] -= 1
	out('\n')


t = int(input())
while t != 0:
	(n, m) = list(map(int, input().split()))
	flavour_count = list(map(int, input().split()))
	waiting_cust = []
	max_profit = 0
	order = []
	x = []
	for i in range(n):
		(d, f, b) = list(map(int, input().split()))
		if flavour_count[d - 1] > 0:
			flavour_count[d - 1] -= 1
			max_profit += f
			order.append(d)
		else:
			max_profit += b
			order.append(0)
	for i in range(m):
		if flavour_count[i] != 0:
			x.append([i, flavour_count[i]])
	for i in range(n):
		if order[i] == 0:
			if x[-1][1] != 0:
				x[-1][1] -= 1
				order[i] = x[-1][0] + 1
			else:
				x.pop()
				x[-1][1] -= 1
				order[i] = x[-1][0] + 1
	print(max_profit)
	print(*order)
	t -= 1


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	l = [0] * n
	total = 0
	for i in range(n):
		(d, f, b) = list(map(int, input().split()))
		if c[d - 1] > 0:
			c[d - 1] -= 1
			total += f
			l[i] = d
		else:
			total += b
	t = m - 1
	print(total)
	for i in l:
		if i > 0:
			print(i, end=' ')
		else:
			while True:
				if c[t] > 0:
					print(t + 1, end=' ')
					c[t] -= 1
					if c[t] == 0:
						t -= 1
					break
				else:
					t -= 1
	print('')


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	C = list(map(int, input().split()))
	ans = [0] * N
	delay = []
	D = [0] * N
	F = [0] * N
	B = [0] * N
	sm = 0
	for i in range(N):
		(D[i], F[i], B[i]) = map(int, input().split())
		if C[D[i] - 1] != 0:
			sm += F[i]
			ans[i] = D[i]
			C[D[i] - 1] -= 1
		else:
			delay.append(i)
	k = 0
	i = 0
	while i < len(delay):
		for k in range(len(C)):
			if i >= len(delay):
				break
			if C[k] == 0:
				continue
			else:
				for fug in range(C[k]):
					if i >= len(delay):
						break
					ans[delay[i]] = k + 1
					sm += B[delay[i]]
					i += 1
	print(sm)
	print(*ans)


t = int(input())
for i in range(t):
	d = []
	f = []
	b = []
	profit = 0
	(n, m) = [int(x) for x in input().split()]
	order = [0 for j in range(n)]
	flav = [int(x) for x in input().split()]
	for j in range(n):
		inp = [int(x) for x in input().split()]
		d.append(inp[0])
		f.append(inp[1])
		b.append(inp[2])
	for j in range(n):
		if flav[d[j] - 1] > 0:
			profit = profit + f[j]
			flav[d[j] - 1] -= 1
			order[j] = d[j]
	flag = 0
	for j in range(n):
		if order[j] == 0:
			for k in range(flag, n):
				if flav[flag] > 0:
					order[j] = flag + 1
					flav[flag] -= 1
					profit += b[j]
					break
				else:
					flag += 1
	print(profit)
	for k in range(len(order) - 1):
		print(order[k], end=' ')
	print(order[-1])


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = [0] + list(map(int, input().split()))
	s = 0
	c = 0
	m1 = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if l[d] > 0:
			m1.append(d)
			s += f
			l[d] -= 1
		else:
			m1.append(0)
			s += b
	for i in range(n):
		if m1[i] == 0:
			for j in range(c, m + 1):
				if l[j] > 0:
					m1[i] = j
					l[j] -= 1
					c = j
					break
	print(s)
	print(*m1)


for _ in range(int(input())):
	(n, ml) = [int(x) for x in input().split()]
	m = [int(x) for x in input().split()]
	prof = 0
	remc = 0
	ans = ['-'] * n
	for i in range(n):
		(d, f, b) = [int(x) for x in input().split()]
		if m[d - 1]:
			m[d - 1] -= 1
			ans[i] = d
			prof += f
		else:
			prof += b
			remc += 1
	remd = []
	for i in range(ml):
		if m[i]:
			remd.extend([i + 1] * m[i])
		if len(remd) >= remc:
			break
	i = 0
	for j in range(n):
		if ans[j] == '-':
			ans[j] = remd[i]
			i += 1
	print(prof)
	print(' '.join([str(x) for x in ans]))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	max_av = list(map(int, input().split()))
	choices_and_price = []
	array = [0] * M
	for i in range(N):
		a = list(map(int, input().split()))
		array[a[0] - 1] += 1
		choices_and_price.append(a)
	left = []
	end = {}
	for i in range(M):
		if max_av[i] > array[i]:
			left.append([i, max_av[i] - array[i]])
	profit = 0
	result_array = []
	for i in range(N):
		p = choices_and_price[i]
		if max_av[p[0] - 1] > 0:
			max_av[p[0] - 1] -= 1
			profit += p[1]
			result_array.append(p[0])
		else:
			profit += p[2]
			k = left[0]
			left[0][1] -= 1
			result_array.append(left[0][0] + 1)
			if left[0][1] == 0:
				left.pop(0)
	print(profit)
	print(*result_array)


from array import *
tc = int(input())
while tc:
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	p = [int(x) for x in input().split(' ')]
	hash_t = []
	for i in range(n):
		(a, b, c) = input().split(' ')
		a = int(a)
		b = int(b)
		c = int(c)
		hash_t.append([a, b, c])
	h = [0] * m
	for i in range(n):
		h[hash_t[i][0] - 1] += 1
	ans = []
	count = []
	index = 0
	for i in range(m):
		diff = int(p[i] - h[i])
		if diff > 0:
			ans.append([i, diff])
	sum = 0
	for i in range(n):
		if p[hash_t[i][0] - 1] > 0:
			p[hash_t[i][0] - 1] -= 1
			sum += hash_t[i][1]
			count.append(hash_t[i][0])
		else:
			sum += hash_t[i][2]
			if ans[index][1] > 0:
				count.append(ans[index][0] + 1)
				ans[index][1] -= 1
			else:
				index += 1
				count.append(ans[index][0] + 1)
				ans[index][1] -= 1
	print(sum)
	for i in range(len(count)):
		print(count[i], end=' ')
	tc -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	k = [0] * n
	ans = 0
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if l[d - 1] != 0:
			l[d - 1] -= 1
			k[i] = d
			ans += f
		else:
			ans += b
	j = 0
	for i in range(m):
		if l[i] != 0:
			while j < n and l[i] > 0:
				if k[j] == 0:
					l[i] -= 1
					k[j] = i + 1
				j += 1
	print(ans)
	print(*k)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	p = 0
	o = []
	x = []
	for i in range(n):
		k = list(map(int, input().split()))
		if l[k[0] - 1] > 0:
			p += k[1]
			l[k[0] - 1] -= 1
			o.append(k[0])
		else:
			o.append(0)
			p += k[2]
			x.append(i)
	j = 0
	i = 0
	while i < n and j < len(x):
		if l[i] > 0:
			o[x[j]] = i + 1
			l[i] -= 1
			j += 1
		else:
			i += 1
	print(p)
	for i in o:
		print(i, end=' ')


try:
	t = int(input())
	while t > 0:
		(n, m) = [int(x) for x in input().split()]
		cust_order = []
		max_profit = 0
		C = list(map(int, input().split()))
		for i in range(n):
			(d, f, b) = map(int, input().split())
			if C[d - 1] > 0:
				C[d - 1] = C[d - 1] - 1
				cust_order.append(d)
				max_profit = max_profit + f
			else:
				cust_order.append(0)
				max_profit = max_profit + b
		firs_drink = 0
		for k in range(len(cust_order)):
			if cust_order[k] != 0:
				continue
			for l in range(firs_drink, len(C)):
				if C[l] > 0:
					cust_order[k] = l + 1
					C[l] = C[l] - 1
					break
				else:
					firs_drink = l + 1
		print(max_profit)
		print(*cust_order)
		t = t - 1
except:
	pass


import random
t = int(input())
while t:
	(n, m) = map(int, input().split())
	drinks = list(map(int, input().split()))
	s = sum(drinks)
	outpt = []
	sm = 0
	k = 0
	remain = []
	q = []
	while n:
		(d, f, b) = map(int, input().split())
		if drinks[d - 1] > 0:
			sm += f
			outpt.append(d)
			drinks[d - 1] -= 1
			k += 1
		else:
			sm += b
			outpt.append(0)
			q.append(k)
			k += 1
		n -= 1
	for i in range(m):
		if drinks[i] != 0:
			remain.append([i, drinks[i]])
	x = 0
	for i in q:
		if remain[x][1] != 0:
			outpt[i] = remain[x][0] + 1
			remain[x][1] -= 1
		else:
			x += 1
			outpt[i] = remain[x][0] + 1
			remain[x][1] -= 1
	print(sm)
	print(*outpt)
	t -= 1


t = input()
for ii in range(int(t)):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	ans = 0
	remain = []
	ansL = [0] * n
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] > 0:
			c[d - 1] -= 1
			ans += f
			ansL[i] = d
		else:
			remain.append((i, d, f, b))
	j = 0
	k = 0
	cc = []
	for i in range(len(c)):
		if c[i] > 0:
			cc.append([i + 1, c[i]])
	j = 0
	for i in range(len(remain)):
		ans += remain[i][3]
		ansL[remain[i][0]] = cc[j][0]
		cc[j][1] -= 1
		if cc[j][1] == 0:
			j += 1
	print(ans)
	for i in range(len(ansL)):
		print(ansL[i], end=' ')
	print()


test = int(input())
for _ in range(test):
	(n, m) = map(int, input().split())
	cx = list(map(int, input().split()))
	dx = []
	fx = []
	bx = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		dx.append(d)
		fx.append(f)
		bx.append(b)
	profit = 0
	order = []
	pending = []
	for i in range(n):
		if cx[dx[i] - 1] > 0:
			cx[dx[i] - 1] -= 1
			profit += fx[i]
			order.append(dx[i])
		else:
			pending.append(i)
			profit += bx[i]
			order.append(0)
	cnt = 0
	flag = 0
	for i in range(m):
		while cx[i] > 0:
			if cnt == len(pending):
				flag = 1
				break
			order[pending[cnt]] = i + 1
			cnt += 1
			cx[i] -= 1
		if flag == 1:
			break
	print(profit)
	print(' '.join((str(x) for x in order)))


x = int(input())
for __ in range(x):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	l = []
	for __ in range(a):
		l.append(list(map(int, input().split())))
	k = 0
	w = [0] * a
	s = 0
	q = []
	for i in range(len(l)):
		if c[l[i][0] - 1] > 0:
			k += l[i][1]
			c[l[i][0] - 1] -= 1
			w[i] = l[i][0]
		else:
			k += l[i][2]
			s += 1
			q.append(i)
	p = 0
	while s > 0:
		while c[p] == 0:
			p += 1
		c[p] -= 1
		w[q[len(q) - 1 - s]] = p + 1
		s -= 1
	print(k)
	print(*w)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	drinks = list(map(int, input().split()))
	output = 0
	remain = []
	olist = [0] * n
	for i in range(n):
		(demand, goodp, badp) = map(int, input().split())
		if drinks[demand - 1] != 0:
			drinks[demand - 1] -= 1
			olist[i] = demand
			output += goodp
		else:
			remain.append(i)
			output += badp
	rj = 0
	for i in range(len(drinks)):
		if drinks[i] == 0:
			continue
		while drinks[i] > 0:
			if rj == len(remain):
				break
			olist[remain[rj]] = i + 1
			rj += 1
			drinks[i] -= 1
		if rj == len(remain):
			break
	print(output)
	for i in olist:
		print(i, end=' ')
	print()


t = int(input())
from collections import defaultdict
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	ba = []
	sa = []
	ans = 0
	hash = defaultdict(list)
	for i in range(n):
		(a, b, c) = map(int, input().split())
		if l[a - 1] != 0:
			hash[i + 1].append(a)
			l[a - 1] -= 1
			ans += b
		else:
			ba.append([c, i + 1])
	for (j, i) in enumerate(l):
		if i != 0:
			sa.append([i, j + 1])
	ba.reverse()
	sa.reverse()
	if sa != []:
		for i in range(len(ba)):
			if sa == []:
				break
			if sa[0][0] != 0:
				ans += ba[i][0]
				hash[ba[i][1]].append(sa[0][1])
				sa[0][0] -= 1
			if sa[0][0] == 0:
				sa.pop(0)
	lo = [0] * n
	for i in hash.keys():
		z = hash[i][0]
		lo[i - 1] = z
	print(ans)
	print(*lo)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	profit = 0
	s = [0] * n
	for j in range(n):
		(d, f, b) = map(int, input().split())
		d = d - 1
		if l[d] > 0:
			profit += f
			l[d] -= 1
			s[j] = str(d + 1)
		else:
			profit += b
	k = 0
	for j in range(n):
		if s[j] == 0:
			while l[k] == 0:
				k += 1
			s[j] = str(k + 1)
			l[k] -= 1
	print(profit)
	k = ' '
	print(k.join(s))


while True:
	try:
		for _ in range(int(input())):
			(n, m) = map(int, input().split())
			max_flavours = list(map(int, input().split()))
			people = []
			for i in range(n):
				people.append([i + 1] + list(map(int, input().split())))
			extra_flavors = [0 for i in range(m)]
			for (person, favorite, favMoney, nonFavMoney) in people:
				extra_flavors[favorite - 1] += 1
			remainingFlavours = []
			for i in range(m):
				extra_flavors[i] = max_flavours[i] - extra_flavors[i]
				remainingFlavours.append([i + 1, extra_flavors[i]])
			_extra_flavours = sorted(remainingFlavours, reverse=True, key=lambda x: x[1])
			profit = 0
			answer = []
			currentExtra = 0
			for (person, favorite, favMoney, nonFavMoney) in people:
				if max_flavours[favorite - 1] > 0:
					profit += favMoney
					answer.append(favorite)
					max_flavours[favorite - 1] -= 1
				else:
					profit += nonFavMoney
					if _extra_flavours[currentExtra][1] == 0:
						currentExtra += 1
						answer.append(_extra_flavours[currentExtra][0])
						_extra_flavours[currentExtra][1] -= 1
					else:
						answer.append(_extra_flavours[currentExtra][0])
						_extra_flavours[currentExtra][1] -= 1
			print(profit)
			print(*answer)
	except (ValueError, EOFError) as e:
		break


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	amt = [int(x) for x in input().split()]
	cost = 0
	brr = [0 for x in range(n)]
	crr = []
	for j in range(n):
		(d, f, b) = [int(x) for x in input().split()]
		if amt[d - 1] > 0:
			amt[d - 1] -= 1
			cost += f
			brr[j] = d
		else:
			crr.append(j)
			cost += b
	r = 0
	for j in crr:
		for k in range(r, m):
			if amt[k] > 0:
				r = k
				amt[k] -= 1
				brr[j] = k + 1
				break
	print(cost)
	for j in range(n - 1):
		print(brr[j], end=' ')
	print(brr[-1])


for t in range(int(input())):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	ans = 0
	ans_li = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] > 0:
			c[d - 1] -= 1
			ans += f
			ans_li += [d]
		else:
			ans_li += ['.']
			ans += b
	ctr = 0
	for ij in range(len(ans_li)):
		if ans_li[ij] == '.':
			while c[ctr] == 0:
				ctr += 1
			ans_li[ij] = ctr + 1
			c[ctr] -= 1
	print(ans)
	print(*ans_li)


def maximize(n, m, c, u):
	sum = 0
	g = [0] * n
	r = []
	for i in range(n):
		if c[u[i][0] - 1] > 0:
			c[u[i][0] - 1] -= 1
			sum += u[i][1]
			g[i] = u[i][0]
		else:
			r.append(i)
			sum += u[i][2]
	ri = 0
	rn = len(r)
	for i in range(m):
		if ri == rn:
			break
		else:
			while c[i] > 0:
				if ri == rn:
					break
				else:
					c[i] -= 1
					g[r[ri]] = i + 1
					ri += 1
	print(sum)
	for (i, gi) in enumerate(g):
		if i < n - 1:
			print(gi, end=' ')
		else:
			print(gi)
t = 0
try:
	t = int(input())
except:
	pass
while t > 0:
	(n, m) = list(map(int, input().rstrip().split()))
	c = list(map(int, input().rstrip().split()))
	u = []
	for i in range(n):
		u.append(list(map(int, input().rstrip().split())))
	maximize(n, m, c, u)
	t -= 1


import sys
from math import ceil, floor
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
rw = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, m) = RI()
	c = RI()
	prof = 0
	ans = [-1] * n
	arr = []
	bs = []
	for i in range(n):
		(f, a, b) = RI()
		f -= 1
		if c[f] >= 1:
			ans[i] = f + 1
			c[f] -= 1
			prof += a
		else:
			arr.append(i)
			bs.append(b)
	for i in range(len(arr)):
		prof += bs[i]
	ite = 0
	for i in range(len(c)):
		if c[i] != 0:
			while c[i] != 0 and ite != len(arr):
				ans[arr[ite]] = i + 1
				c[i] -= 1
				ite += 1
		if ite == len(arr):
			break
	print(prof)
	print(' '.join(map(str, ans)))


T = int(input())
for t in range(0, T):
	(N, M) = input().split(' ')
	C = list(map(int, input().split()))
	DFB = []
	profit = 0
	Ccopy = C.copy()
	lst = []
	x = []
	for i in range(int(N)):
		DFB.append(list(map(int, input().split())))
	for i in range(int(N)):
		if C[DFB[i][0] - 1] > 0:
			C[DFB[i][0] - 1] -= 1
			profit += DFB[i][1]
			lst.append(DFB[i][0])
		else:
			profit += DFB[i][2]
			lst.append(0)
	for i in range(int(M)):
		if C[i] != 0:
			x.append([i, C[i]])
	for i in range(int(N)):
		if lst[i] == 0:
			if x[-1][1] != 0:
				x[-1][1] -= 1
				lst[i] = x[-1][0] + 1
			else:
				x.pop()
				x[-1][1] -= 1
				lst[i] = x[-1][0] + 1
	print(profit)
	print(*lst)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(0, t):
	p = 0
	h = 0
	z = []
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	for j in range(0, n):
		(d, c, b) = list(map(int, input().split()))
		if a[d - 1] > 0:
			p = p + c
			z.append(d)
			a[d - 1] -= 1
		else:
			p = p + b
			z.append(0)
	print(p)
	for j in range(0, n):
		if z[j] != 0:
			print(z[j], end=' ')
		else:
			while a[h] == 0:
				h += 1
			print(h + 1, end=' ')
			a[h] -= 1


from collections import defaultdict as dc
for _ in range(int(input())):
	bill = 0
	(n, m) = [int(i) for i in input().split()]
	c = [int(i) for i in input().split()]
	p = 0
	a = []
	for i in range(n):
		(d, b, f) = [int(i) for i in input().split()]
		if c[d - 1] > 0:
			bill += b
			c[d - 1] -= 1
			a.append(d)
		else:
			bill += f
			p += 1
			a.append('c')
	l = []
	for i in range(m):
		if c[i] > 0:
			l = l + [i + 1] * c[i]
			p = p - c[i]
		if p <= 0:
			break
	j = 0
	for i in range(n):
		if a[i] == 'c':
			a[i] = l[j]
			j += 1
	print(bill)
	print(*a)


for e in range(int(input())):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	pf = 0
	sale = [0] * n
	hold = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] != 0:
			sale[i] = d
			pf += f
			c[d - 1] -= 1
		else:
			hold += [[i, b]]
	for i in range(m):
		flag = 0
		if c[i] > 0:
			for j in range(c[i]):
				if hold == []:
					flag = 1
					break
				sale[hold[0][0]] = i + 1
				pf += hold[0][1]
				hold.pop(0)
		if flag == 1:
			break
	print(pf)
	print(*sale)


T = int(input())
for _ in range(T):
	(n, m) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	q = []
	p = 0
	y = 0
	x = []
	for i in range(n):
		(d, f, b) = list(map(int, input().split()))
		if c[d - 1] > 0:
			c[d - 1] -= 1
			p += f
			q += [d]
		else:
			q += [-1]
			y += 1
			p += b
	for i in range(m):
		if c[i] != 0:
			x += [[i, c[i]]]
	for i in range(n):
		if q[i] == -1:
			if x[-1][1] > 0:
				x[-1][1] -= 1
				q[i] = x[-1][0] + 1
			else:
				x.pop()
				x[-1][1] -= 1
				q[i] = x[-1][0] + 1
	print(p)
	print(*q)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	flav = list(map(int, input().split()))
	ans = []
	res = 0
	k = 0
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if flav[d - 1] == 0:
			res += b
			ans.append(-1)
			k += 1
		else:
			flav[d - 1] -= 1
			res += f
			ans.append(d)
	l = []
	for i in range(m):
		while flav[i] != 0 and k != 0:
			flav[i] -= 1
			k -= 1
			l.append(i + 1)
	print(res)
	c = 0
	for i in range(n):
		if ans[i] == -1:
			print(l[c], end=' ')
			c += 1
		else:
			print(ans[i], end=' ')
	print()


def get(arr, i, m):
	while i <= m:
		if arr[i] > 0:
			return i
		i += 1
for t in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	arr.insert(0, 0)
	profit = 0
	res = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if arr[d] > 0:
			profit += f
			arr[d] -= 1
			res.append(d)
		else:
			profit += b
			res.append(-1)
	print(profit)
	id = 1
	for i in res:
		if i != -1:
			print(i, end=' ')
		else:
			id = get(arr, id, m)
			print(id, end=' ')
			arr[id] -= 1
	print()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	c = [int(j) for j in input().split(' ')]
	revenue = 0
	finallist = []
	remlist = []
	p = 0
	customer = []
	for j in range(n):
		customer.append([int(j) for j in input().split(' ')])
		if c[customer[j][0] - 1] > 0:
			revenue += customer[j][1]
			finallist.append(customer[j][0])
			c[customer[j][0] - 1] -= 1
		else:
			remlist.append(p)
		p += 1
	k = 0
	while len(remlist):
		if c[k] > 0:
			revenue += customer[remlist[0]][2]
			finallist.insert(remlist[0], k + 1)
			c[k] -= 1
			remlist.remove(remlist[0])
		else:
			k += 1
	print(revenue)
	print(*finallist, sep=' ')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	a = [0 for _ in range(n)]
	p = 0
	for j in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] > 0:
			c[d - 1] = c[d - 1] - 1
			p = p + f
			a[j] = d
		else:
			p = p + b
	k = 0
	j = 0
	while j < n:
		if a[j] == 0 and c[k] != 0:
			a[j] = k + 1
			c[k] = c[k] - 1
		elif a[j] == 0 and c[k] == 0:
			k = k + 1
			j = j - 1
		j = j + 1
	print(p)
	print(*a)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	av = list(map(int, input().split()))
	dem = {}
	for i in range(m):
		dem[i + 1] = av[i]
	s = 0
	l = [-1] * n
	left = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if d in dem:
			s += f
			dem[d] -= 1
			l[i] = d
			if dem[d] == 0:
				del dem[d]
		else:
			s += b
			left.append(i)
	for i in left:
		for j in dem:
			l[i] = j
			dem[j] -= 1
			if dem[j] == 0:
				del dem[j]
			break
	print(s)
	for i in l:
		print(i, end=' ')


T = int(input())
for t in range(T):
	(N, M) = list(map(int, input().split()))
	c = list(map(int, input().split()))
	likes = [0 for i in range(M)]
	fs = []
	bs = []
	ds = []
	for n in range(N):
		(d, f, b) = list(map(int, input().split()))
		ds.append(d)
		likes[d - 1] += 1
		fs.append(f)
		bs.append(b)
	stock = []
	for i in range(M):
		stock.append([i, c[i] - likes[i]])
	stock.sort(reverse=True, key=lambda x: x[1])
	profit = 0
	ans = []
	for i in range(N):
		if c[ds[i] - 1] > 0:
			c[ds[i] - 1] -= 1
			ans.append(ds[i])
			profit += fs[i]
		else:
			ans.append(stock[0][0] + 1)
			stock[0][1] -= 1
			if stock[0][1] == 0:
				stock.pop(0)
			profit += bs[i]
	print(profit)
	print(' '.join(map(str, ans)))


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	(s, c, r) = ([], 0, 0)
	t = [int(x) for x in input().split()]
	b = [0 for i in range(N)]
	for j in range(N):
		s.append([int(y) for y in input().split()])
		if t[s[j][0] - 1] > 0:
			t[s[j][0] - 1] -= 1
			c += s[j][1]
			b[j] = s[j][0]
	for j in range(N):
		if b[j] == 0:
			for k in range(r, M):
				if t[k] > 0:
					r = k
					t[k] -= 1
					c += s[j][2]
					b[j] = k + 1
					break
	print(c)
	for j in range(N - 1):
		print(b[j], end=' ')
	print(b[-1])


testcase = int(input())
for i in range(testcase):
	(n, m) = input().split()
	(n, m) = [int(n), int(m)]
	c = [int(i) for i in input().split()]
	dg = []
	l2 = []
	output = [0] * n
	count = 0
	for j in range(n):
		(d, f, b) = input().split()
		(d, f, b) = [int(d), int(f), int(b)]
		l2.append([d, f, b])
		if c[d - 1] > 0:
			output[j] = d
			count += f
			c[d - 1] -= 1
		else:
			count += b
	for i in range(m):
		if c[i] > 0:
			dg.append(i + 1)
	for i in range(n):
		if output[i] == 0:
			output[i] = dg[0]
			c[dg[0] - 1] -= 1
			if c[dg[0] - 1] == 0:
				dg = dg[1:]
	print(count)
	print(' '.join([str(i) for i in output]))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	m1 = list(map(int, input().split()))
	d = []
	f = []
	b = []
	res = [0] * n
	profit = 0
	for i in range(n):
		(d1, f1, b1) = map(int, input().split())
		d.append(d1)
		f.append(f1)
		b.append(b1)
		x = d[i]
		if m1[x - 1] > 0:
			res[i] = x
			m1[x - 1] = m1[x - 1] - 1
			profit = profit + f[i]
		else:
			res[i] = -100
			profit = profit + b[i]
	print(profit)
	k = 0
	for j in range(n):
		if res[j] != -100:
			print(res[j], end=' ')
		else:
			while m1[k] == 0:
				k += 1
			print(k + 1, end=' ')
			m1[k] -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0] * (m + 1)
	assign = [0] * (n + 1)
	s = 0
	k = list(map(int, input().split()))
	for i in range(m):
		l[i + 1] = k[i]
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if l[d] > 0:
			l[d] -= 1
			s += f
			assign[i] = d
		else:
			s += b
	j = 0
	while l[j] == 0:
		j += 1
	for i in range(n):
		if assign[i] == 0:
			if l[j] != 0:
				l[j] -= 1
				assign[i] = j
			else:
				while l[j] == 0:
					j += 1
				l[j] -= 1
				assign[i] = j
	print(s)
	for i in range(n):
		print(assign[i], end=' ')
	print()


try:
	for _ in range(int(input())):
		(n, m) = map(int, input().split(' '))
		ans = [0 for i in range(n)]
		ans1 = 0
		capacity = list(map(int, input().split(' ')))
		for i in range(n):
			(d, f, b) = list(map(int, input().split(' ')))
			if capacity[d - 1] > 0:
				ans1 += f
				ans[i] = d
				capacity[d - 1] -= 1
			else:
				ans1 += b
		capacity = list(enumerate(capacity, 1))
		capacity = filter(lambda x: x[1] > 0, capacity)
		capacity = list(capacity)
		ele = capacity[0][1]
		for i in range(n):
			if ans[i] == 0:
				if ele == 0:
					del capacity[0]
					ele = capacity[0][1]
				ans[i] = capacity[0][0]
				ele -= 1
		print(ans1)
		for i in ans:
			print(i, end=' ')
except Exception as e:
	pass


for T in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * n
	ind = [0] * (n + 1)
	Di = [0] * (n + 1)
	Fi = [0] * (n + 1)
	Bi = [0] * (n + 1)
	cost = 0
	for i in range(n):
		(di, fi, bi) = map(int, input().split())
		Di[i] = di
		Fi[i] = fi
		Bi[i] = bi
		di = di - 1
		if a[di] != 0:
			a[di] = a[di] - 1
			ind[i] = 1
			cost = cost + Fi[i]
			b[i] = Di[i]
		else:
			ind[i] = 0
			cost = cost + Bi[i]
	t = 0
	for i in range(n):
		if b[i] == 0:
			while a[t] == 0:
				t = t + 1
			b[i] = t + 1
			a[t] = a[t] - 1
	print(cost)
	print(*b)


t = int(input())
for x in range(t):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	costs = []
	total = 0
	indices = []
	left = []
	for y in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] > 0:
			c[d - 1] = c[d - 1] - 1
			total = total + f
			costs.append(d)
		else:
			costs.append(0)
			indices.append([y, b])
	for y in range(len(c)):
		if c[y] > 0:
			left.append([y + 1, c[y]])
	x = 0
	for y in range(len(indices)):
		if left[x][1] == 0:
			x = x + 1
		costs[indices[y][0]] = left[x][0]
		left[x][1] = left[x][1] - 1
		total = total + indices[y][1]
	print(total)
	print(*costs, sep=' ')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	c = [int(x) for x in input().split()]
	d = []
	f = []
	b = []
	for i in range(n):
		(a1, b1, c1) = map(int, input().split())
		d.append(a1)
		f.append(b1)
		b.append(c1)
	mp = 0
	ans = []
	for i in range(n):
		if c[d[i] - 1] > 0:
			mp = mp + f[i]
			c[d[i] - 1] = c[d[i] - 1] - 1
			ans.append(d[i])
		else:
			mp = mp + b[i]
			ans.append(-1)
	print(mp)
	j = 0
	for i in range(n):
		if ans[i] != -1:
			print(ans[i], end=' ')
		else:
			while c[j] == 0:
				j += 1
			print(j + 1, end=' ')
			c[j] -= 1


t = int(input())
while t:
	t -= 1
	s = 0
	r = []
	a = input().split()
	b = list(map(int, input().split()))
	for i in range(int(a[0])):
		c = list(map(int, input().split()))
		if b[c[0] - 1] > 0:
			s += c[1]
			b[c[0] - 1] -= 1
			r += [c[0]]
		else:
			s += c[2]
			r += [-10]
	print(s)
	tt = 0
	for i in range(int(a[0])):
		if r[i] != -10:
			print(r[i], end=' ')
		else:
			while b[tt] == 0:
				tt += 1
			print(tt + 1, end=' ')
			b[tt] -= 1
	print()


class Solution(object):

	def __init__(self):
		self.tests = int(input())
		self.num_customers = 0
		self.num_flavors = 0
		self.flavors = []
		self.d = []
		self.f = []
		self.b = []
		self.ans = []
		self.chosen_flavors = []
		for _ in range(self.tests):
			self.get_data()
			self.solve()
			self.print_output()
			self.clear_data()
	pass

	def get_data(self):
		(self.num_customers, self.num_flavors) = map(int, input().split())
		self.ans = [0] * self.num_customers
		self.chosen_flavors = [0] * self.num_customers
		self.flavors = [0] + list(map(int, input().split()))
		for _ in range(self.num_customers):
			(d, f, b) = map(int, input().split())
			self.d.append(d)
			self.f.append(f)
			self.b.append(b)
		pass

	def clear_data(self):
		self.flavors.clear()
		self.d.clear()
		self.f.clear()
		self.b.clear()
		self.ans.clear()
		self.chosen_flavors.clear()
		pass

	def print_output(self):
		print(sum(self.ans))
		for x in self.chosen_flavors:
			print(x, end=' ')
		pass

	def solve(self):
		for i in range(self.num_customers):
			if self.flavors[self.d[i]]:
				self.ans[i] = self.f[i]
				self.flavors[self.d[i]] -= 1
				self.chosen_flavors[i] = self.d[i]
		begin = 1
		for i in range(len(self.chosen_flavors)):
			if self.chosen_flavors[i] == 0:
				for j in range(begin, self.num_flavors + 1):
					if self.flavors[j]:
						self.ans[i] = self.b[i]
						self.flavors[j] -= 1
						self.chosen_flavors[i] = j
						begin = j
						break
		pass

def main():
	Solution()
	pass
main()


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	sum = 0
	res = []
	for _ in range(n):
		(d, f, b) = [int(x) for x in input().split()]
		if c[d - 1] > 0:
			c[d - 1] -= 1
			sum += f
			res.append(d)
		elif c[d - 1] == 0:
			res.append(0)
			sum += b
	for y in range(len(c)):
		if c[y] != 0:
			m = y
			break
	for x in range(len(res)):
		if res[x] == 0:
			for y in range(m, len(c)):
				if c[y] > 0:
					res[x] = y + 1
					c[y] -= 1
					break
				else:
					m += 1
	print(sum)
	l = [print(i, end=' ') for i in res]


for i in range(int(input())):
	(nn, m) = map(int, input().split())
	c = list(map(int, input().split()))
	d = dict()
	pro = 0
	arr = [0] * nn
	k = 0
	hold = []
	while nn > 0:
		nn -= 1
		(l, m, n) = map(int, input().split())
		if c[l - 1] > 0:
			pro += m
			arr[k] = l
			c[l - 1] -= 1
		else:
			pro += n
			hold.append(k)
		k += 1
	cou = len(hold)
	for i in range(len(c)):
		if c[i] > 0:
			while c[i] > 0:
				c[i] -= 1
				if hold == []:
					cou = 0
					break
				arr[hold[0]] = i + 1
				hold.pop(0)
				cou -= 1
				if cou < 1:
					break
		if cou < 1:
			break
	print(pro)
	for i in range(len(arr)):
		print(arr[i], end=' ')


t = int(input())
for i in range(0, t):
	Sum = 0
	freq = []
	(n, m) = map(int, input().split())
	ans = [0] * n
	freq = [int(x) for x in input().split()]
	for k in range(1, n + 1):
		val = list(map(int, input().split()))
		if freq[val[0] - 1] != 0:
			ans[k - 1] = val[0]
			Sum = Sum + val[1]
			freq[val[0] - 1] -= 1
		else:
			Sum = Sum + val[2]
	f = 1
	p = 1
	while f <= m and p <= n:
		if ans[p - 1] == 0 and freq[f - 1] != 0:
			ans[p - 1] = f
			p += 1
			freq[f - 1] -= 1
		elif freq[f - 1] == 0:
			f += 1
		else:
			p += 1
	print(Sum)
	for g in ans:
		print(g, end=' ')


t = int(input())
for i in range(t):
	(n, m) = map(int, input().strip().split(' '))
	ar_m = [int(x) for x in input().split()]
	count = 0
	ar_res = []
	temp = []
	q = 0
	for j in range(n):
		(d, f, b) = map(int, input().strip().split(' '))
		if ar_m[d - 1] != 0:
			count += f
			ar_res.append(d)
			ar_m[d - 1] -= 1
		else:
			count += b
			temp.append(j)
			q += 1
	k = 0
	index = 0
	while k != q:
		for j in range(index, m):
			if ar_m[j] != 0:
				ar_res.insert(temp[k], j + 1)
				k += 1
				ar_m[j] -= 1
				index = j
				break
	print(count)
	for j in range(n):
		print(ar_res[j], end=' ')
	print(' ')


for t in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	x = []
	ans = []
	cost = 0
	rem = []
	for i in range(n):
		c = list(map(int, input().split()))
		x.append(c)
	for i in range(len(x)):
		if l[x[i][0] - 1] > 0:
			l[x[i][0] - 1] -= 1
			ans.append(x[i][0])
			cost += x[i][1]
		else:
			rem.append(i)
			cost += x[i][2]
	q = 0
	k = 0
	while k < len(rem):
		if l[q] > 0:
			ans.insert(rem[k], q + 1)
			l[q] -= 1
			k += 1
		else:
			q += 1
	print(cost)
	print(*ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	l = []
	ans = 0
	for z in range(n):
		(d, f, b) = map(int, input().split())
		l.append([d, f, b])
	v = [0] * len(l)
	res = [0] * n
	a = []
	for (j, i) in enumerate(l):
		if c[i[0] - 1] > 0:
			c[i[0] - 1] -= 1
			ans += i[1]
			v[j] = 1
			res[j] = i[0]
	s = len(l)
	lc = len(c)
	count = 0
	for i in range(s):
		if v[i] == 0:
			ans += l[i][2]
			count += 1
	k = []
	for i in range(lc):
		if c[i] > 0:
			while c[i] > 0 and count > 0:
				c[i] -= 1
				count -= 1
				k.append(i + 1)
	kl = len(res)
	for i in range(kl):
		if res[i] == 0:
			res[i] = k.pop()
	print(ans)
	for i in res:
		print(i, end=' ')
	print()


t = int(input())
while t > 0:
	t = t - 1
	(n, m) = map(int, input().split())
	s = 0
	arr = []
	arrm = [int(m) for m in input().split()]
	for i in range(n):
		(d, v, c) = map(int, input().split())
		if arrm[d - 1] != 0:
			s = s + v
			arr.append(d)
			arrm[d - 1] = arrm[d - 1] - 1
		else:
			s = s + c
			arr.append(0)
	print(s)
	arr1 = []
	for i in range(m):
		if arrm[i] != 0:
			arr1.append([i + 1, arrm[i]])
	j = 0
	for i in range(n):
		if arr[i] == 0:
			arr[i] = arr1[j][0]
			arr1[j][1] = arr1[j][1] - 1
			if arr1[j][1] == 0:
				j = j + 1
		print(arr[i], end=' ')


t = int(input())

def printlist(ll):
	st = ''
	for i in ll:
		st += str(i) + ' '
	return st
for x in range(0, t):
	profit = 0
	(n, m) = map(int, input().split())
	fos = [0] * n
	tbd = []
	flavours = list(map(int, input().split()))
	for y in range(0, n):
		(d, f, b) = map(int, input().split())
		if flavours[d - 1] > 0:
			flavours[d - 1] = flavours[d - 1] - 1
			profit += f
			fos[y] = d
		else:
			tbd.append(y)
			profit += b
	c = 0
	for y in range(0, len(flavours)):
		while flavours[y] > 0 and c < len(tbd):
			fos[tbd[c]] = y + 1
			flavours[y] -= 1
			c += 1
		if c >= len(tbd):
			break
	print(profit)
	print(printlist(fos))


t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	rd = {}
	profit = 0
	lessprofit = 0
	ans = []
	remaining = []
	for i in range(n):
		(di, fi, bi) = map(int, input().split())
		if c[di - 1] > 0:
			c[di - 1] -= 1
			profit += fi
			ans.append(di)
		else:
			lessprofit += bi
			ans.append(-1)
	print(profit + lessprofit)
	j = 0
	for i in range(n):
		if ans[i] == -1:
			while c[j] == 0:
				j += 1
			ans[i] = j + 1
			c[j] -= 1
	print(*ans)


from sys import stdin, stdout
input = stdin.readline
for T in range(int(input())):
	(N, M) = map(int, input().split())
	C = list(map(int, input().split()))
	profit = 0
	order = [-1] * N
	for i in range(N):
		(D, F, B) = map(int, input().split())
		if C[D - 1] > 0:
			profit += F
			C[D - 1] -= 1
			order[i] = D
		else:
			profit += B
	remaining = {}
	for i in range(M):
		if C[i] > 0:
			remaining[i + 1] = C[i]
	id = 0
	keys = list(remaining.keys())
	count = 0
	for i in range(N):
		if order[i] == -1:
			key = keys[id]
			order[i] = key
			count += 1
			if remaining[key] == count:
				id += 1
				count = 0
	print(profit)
	print(*order)


t = int(input())
for x in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	m = inp[1]
	d = []
	f = []
	b = []
	answer = []
	profit = 0
	number = list(map(int, input().split()))
	for i in range(n):
		flavor = list(map(int, input().split()))
		d.append(flavor[0])
		f.append(flavor[1])
		b.append(flavor[2])
	for cust in range(n):
		if number[d[cust] - 1] > 0:
			answer.append(d[cust])
			number[d[cust] - 1] -= 1
			profit += f[cust]
		else:
			answer.append(0)
	for j in range(len(number)):
		if number[j] > 0:
			break
	for index in range(len(answer)):
		if answer[index] == 0:
			answer[index] = j + 1
			number[j] -= 1
			profit += b[index]
			if number[j] == 0:
				while number[j] == 0:
					j += 1
					if j == m:
						break
	print(profit)
	print(*answer)


for _ in range(int(input().strip())):
	(n, m) = map(int, input().strip().split())
	freq = [0] + list(map(int, input().strip().split()))
	ans = [0] * n
	total = 0
	for i in range(n):
		(d, f, b) = map(int, input().strip().split())
		if freq[d]:
			total += f
			freq[d] -= 1
			ans[i] = d
		else:
			total += b
	ind = 0
	for i in range(n):
		if ans[i] == 0:
			while freq[ind] == 0:
				ind += 1
			ans[i] = ind
			freq[ind] -= 1
	print(total)
	print(*ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	l = []
	o = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if a[d - 1] > 0:
			c += f
			a[d - 1] -= 1
			o.append(d)
		else:
			c += b
			o.append(0)
	print(c)
	w = []
	for h in range(len(a)):
		if a[h] != 0:
			w.append([h, a[h]])
	ijkl = 0
	for lm in range(len(o)):
		if o[lm] == 0:
			if w[ijkl][1] != 0:
				o[lm] = w[ijkl][0] + 1
				w[ijkl][1] -= 1
			else:
				ijkl += 1
				o[lm] = w[ijkl][0] + 1
				w[ijkl][1] -= 1
	print(*o)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	k = a.copy()
	c = 0
	o = []
	remain = []
	for j in range(n):
		(d, f, b) = map(int, input().split())
		if a[d - 1] > 0:
			c = c + f
			o.append(d)
			a[d - 1] -= 1
		else:
			c = c + b
			o.append(0)
			remain.append(j)
		if k[d - 1] > 0:
			k[d - 1] -= 1
	for j in range(len(a)):
		if a[j] > 0:
			while a[j] > 0 and remain != []:
				o[remain.pop()] = j + 1
				a[j] -= 1
	print(c)
	print(' '.join(map(str, o)))
	t = t - 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	c = []
	c = list(map(int, input().split()))
	req = []
	ans = 0
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] > 0:
			c[d - 1] -= 1
			ans += f
			req.append(d)
		else:
			ans += b
			req.append(0)
	excess = []
	for x in range(len(c)):
		if c[x] > 0:
			excess.append([x, c[x]])
	pointer = 0
	for i in range(len(req)):
		if req[i] == 0:
			if excess[pointer][1] > 0:
				req[i] = excess[pointer][0] + 1
				excess[pointer][1] -= 1
			else:
				pointer += 1
				req[i] = excess[pointer][0] + 1
				excess[pointer][1] -= 1
	print(ans)
	print(*req)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	c = list(map(int, input().split()))
	que = []
	ans = [-1] * n
	count = 0
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if c[d - 1] != 0:
			c[d - 1] -= 1
			ans[i] = d
			count += f
		else:
			que.append([i, b])
	qptr = 0
	lenq = len(que)
	for i in range(m):
		csvalue = c[i]
		flag = 0
		if c[i] > 0:
			for j in range(csvalue):
				if qptr == lenq:
					flag = 1
					break
				chotulist = que[qptr]
				ans[chotulist[0]] = i + 1
				count += chotulist[1]
				qptr += 1
				if qptr == lenq:
					flag = 1
					break
		if flag == 1:
			break
	print(count)
	print(*ans)


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	arr = []
	amt = [int(x) for x in input().split()]
	cost = 0
	brr = [0 for i in range(n)]
	for j in range(n):
		arr.append([int(y) for y in input().split()])
		if amt[arr[j][0] - 1] > 0:
			amt[arr[j][0] - 1] -= 1
			cost += arr[j][1]
			brr[j] = arr[j][0]
	r = 0
	for j in range(n):
		if brr[j] == 0:
			for k in range(r, m):
				if amt[k] > 0:
					r = k
					amt[k] -= 1
					cost += arr[j][2]
					brr[j] = k + 1
					break
	print(cost)
	for j in range(n - 1):
		print(brr[j], end=' ')
	print(brr[-1])


T = int(input())
while T > 0:
	(N, M) = list(map(int, input().split()))
	Ci = list(map(int, input().split()))
	prof = 0
	order = [0] * N
	for i in range(N):
		(D, F, B) = map(int, input().split())
		if Ci[D - 1] > 0:
			prof += F
			Ci[D - 1] -= 1
			order[i] = D
		else:
			prof += B
			order[i] = 0
	stock = []
	for i in range(M):
		if Ci[i] != 0:
			stock.append([i, Ci[i]])
	k = 0
	for i in range(N):
		if order[i] == 0:
			order[i] = stock[k][0] + 1
			stock[k][1] -= 1
			if stock[k][1] == 0:
				k += 1
	print(prof)
	print(*order)
	T -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	count = list(map(int, input().split()))
	profit = 0
	aux = []
	ans = [0] * n
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if f >= b and count[d - 1] > 0:
			count[d - 1] -= 1
			profit += f
			ans[i] = d
		else:
			aux.append((i, b))
	pos = 0
	for i in aux:
		while count[pos] == 0:
			pos += 1
		count[pos] -= 1
		profit += i[1]
		ans[i[0]] = pos + 1
	print(profit)
	print(*ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	temp = n
	lol = []
	profit = 0
	while temp > 0:
		(d, f, b) = map(int, input().split())
		if l[d - 1] > 0:
			profit += f
			l[d - 1] -= 1
			lol.append(d)
		else:
			lol.append(-100)
			profit += b
		temp -= 1
	print(profit)
	j = 0
	for i in range(n):
		if lol[i] != -100:
			print(lol[i], end=' ')
		else:
			while l[j] == 0:
				j += 1
			print(j + 1, end=' ')
			l[j] -= 1


def m():
	t = int(input())
	while t > 0:
		(n, m) = map(int, input().split())
		flavours = list(map(int, input().split()))
		count = 0
		contents = []
		final = []
		ind = []
		for i in range(n):
			a = list(map(int, input().split()))
			contents.append(a)
		cost = 0
		for i in range(n):
			if flavours[contents[i][0] - 1] != 0:
				cost += contents[i][1]
				flavours[contents[i][0] - 1] -= 1
				final.append(contents[i][0])
			elif flavours[contents[i][0] - 1] == 0:
				cost += contents[i][2]
				count += 1
				final.append('x')
				ind.append(i)
		j = 0
		for i in range(count):
			while j < m:
				if flavours[j] == 0:
					j += 1
				elif flavours[j] != 0:
					flavours[j] -= 1
					final[ind[i]] = j + 1
					break
		print(cost)
		for i in range(n):
			print(final[i], end=' ')
		t -= 1
m()


t = int(input())
while t:
	(n, m) = map(int, input().split())
	M = list(map(int, input().split()))
	profit = 0
	order = []
	for i in range(n):
		(d, f, b) = map(int, input().split())
		if M[d - 1] > 0:
			M[d - 1] -= 1
			profit += f
			order.append(d)
		else:
			profit += b
			order.append(0)
	print(profit)
	remaining = []
	for i in range(m):
		if M[i] != 0:
			remaining.append([i, M[i]])
	k = 0
	for i in range(n):
		if order[i] != 0:
			print(order[i], end=' ')
		else:
			print(remaining[k][0] + 1, end=' ')
			remaining[k][1] -= 1
			if remaining[k][1] == 0:
				k += 1
	print()
	t -= 1