Read problems statements in mandarin chinese, russian and vietnamese as well. 

The placements/recruitment season is going on in various colleges. The interviews are over, and each company has selected some students. But since each student can end up finally in at most one company, a student might have to reject a company which selected him. The companies know this, and hence, the companies usually select more students than it can actually employ. So now, the exact pairings should be done. We talk about one such session in a famous college.

There are a total of N candidates (numbered from 1 to N) and M companies (numbered from 1 to M) taking part in it. Each candidate has a certain minimum expectation of salary, which is given by the array minSalary (All the arrays are 1-indexed). For each candidate, you are also given the information regarding the companies which have selected him. This information is given by an array qual of size N * M, where qual[i][j] = 1 if and only if the i-th candidate has qualified for a job in the j-th company. A company will provide a fixed salary to the candidates it employs, which is given by the array offeredSalary. Also, a company has an upper bound on the number of candidates it can employ and finally give an offer to. This information is provided by array maxJobOffers.

The D-day has come. Each candidate from 1, 2, .. N (in this order) will go to the placements coordinator. When the i-th student goes, among the companies which have selected him, and which still haven't reached their maxJobOffers limit, he picks the company which provides the maximum offeredSalary, provided that it is at least his minSalary. 

You have to find the number of the candidates that will end up with a job, the total amount of salaries that the candidates will get, and the number of companies that won't be able to employ even a single candidate. This information is very crucial for the placement coordinator, so as to analyze whether it makes sense to invite a company to come to the placements session next year or not. Please help the coordinator!

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows
First line of each test case contains two space separated integer N, M.
The next line contains N space separated integers denoting the array minSalary.
Each of the next M lines contains two space separated integers denoting offeredSalary[i] and maxJobOffers[i].
The next N lines will contain the description of the 2-D array qual. Each of the N lines will contain M binary integers (without any space): j-th integer in the i-th line will denote qual[i][j].

------ Output ------ 

For each test case, output three integers in a new line, denoting the number of the candidates that will get a job, the total amount of salaries that the candidates will get, and the number of companies that won't be able to hire even a single candidate.

------ Constraints ------ 

1 ≤ T ≤ 10
1 ≤ N, M ≤ 10^{3}
0 ≤ minSalary[i] ≤ 10^{9}
0 ≤ qual[i][j] ≤ 1
1 ≤ offeredSalary[i] ≤ 10^{9}
1 ≤ maxJobOffers[i] ≤ 10^{6}
All elements of the array offeredSalary are distinct

------ Subtasks ------ 

Subtask 1 (30 points): 1 ≤ N, M ≤ 200
Subtask 2 (70 points): Original Constraints

----- Sample Input 1 ------ 
1

5 6

5000 10000 3000 20 100

10000 2

800 2

600 1

10 8

1000 9

2000 10

111111

100000

000000

000001

100100
----- Sample Output 1 ------ 
3 22000 4
----- explanation 1 ------ 
There are 5 candidates and 6 companies. 
The first candidate wants a job that pays at least 5000 Rs. He has qualified in all the companies, so he will choose the 1st company that provides him the maximum money, 10000 Rs.
The second candidate will get a job offer of 10000 Rs from 1st company.
The third candidate has not qualified in any company, so he won't get any job.
The fourth candidate has qualified only in 6-th company which provides a salary of 2000 Rs which is greater than or equal to 20, the minimum salary expected by the fourth candidate.
The fifth candidate wants minimum salary 100 Rs. He has qualified in company 1st and 4th. The 1st company won't hire him as it has already filled the quota of hiring two people. 4th company is providing the candidate less than 100 Rs, so he won't join that too.
So, overall there are three candidates that got the job (first, second and fourth). Total amount of salary is 10000 + 10000 + 2000 = 22000. Only first and 6-th companies are able to select some candidates, so there are 4 companies that are not able to hire any candidate. Hence, the answer will be 3 22000 4.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
def solution():
	(N, M) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	offeredSalary = []
	maxJobOffers = []
	for i in range(M):
		(salary, offer) = map(int, input().split())
		offeredSalary.append(salary)
		maxJobOffers.append(offer)
	qual = []
	for i in range(N):
		qual.append([c == '1' for (i, c) in enumerate(input())])
	placements_count = 0
	total_salary = 0
	hiring_companies = set()
	for i in range(N):
		selected = -1
		for j in range(M):
			if qual[i][j] and maxJobOffers[j] > 0 and (offeredSalary[j] >= minSalary[i]):
				if selected == -1 or offeredSalary[selected] < offeredSalary[j]:
					selected = j
		if selected >= 0:
			maxJobOffers[selected] -= 1
			placements_count += 1
			total_salary += offeredSalary[selected]
			hiring_companies.add(selected)
	print(placements_count, end=' ')
	print(total_salary, end=' ')
	print(M - len(hiring_companies))
T = int(input())
while T > 0:
	T = T - 1
	solution()


import sys
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(m):
		d = input().split()
		l1.append(list(map(int, d)))
	ll = []
	for i in range(m):
		ll.append(l1[i][1])
	t = 0
	student = 0
	for i in range(n):
		s = input()
		lik = -1 * sys.maxsize
		max1 = -1 * sys.maxsize
		index = -1
		for j in range(m):
			if s[j] == '1':
				if l1[j][1] > 0:
					if l1[j][0] >= l[i] and l1[j][0] > max1:
						index = j
						max1 = l1[j][0]
		if lik != max1:
			t += max1
		if index != -1:
			l1[index][1] -= 1
			student += 1
	note = 0
	for i in range(m):
		if l1[i][1] == ll[i]:
			note += 1
	print(student, t, note)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	min_salary = [int(j) for j in input().split(' ')]
	company = []
	for j in range(m):
		(offered_salary, max_job_offers) = map(int, input().split())
		company.append([offered_salary, max_job_offers])
	qual = []
	for j in range(n):
		qual.append(list(input()))
	count = 0
	sum_sal = 0
	check = []
	for j in range(n):
		sal = 0
		for k in range(m):
			if qual[j][k] == '1' and company[k][0] >= min_salary[j] and (company[k][1] > 0):
				if company[k][0] > sal:
					sal = company[k][0]
					temp = k
		if sal:
			count += 1
			company[temp][1] -= 1
			sum_sal += sal
			if temp not in check:
				check.append(temp)
	print(str(count) + ' ' + str(sum_sal) + ' ' + str(m - len(check)))


for t in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	offeredsalary = [0] * m
	maxjoboffer = [0] * m
	minsalary = [int(i) for i in input().split()]
	for i in range(m):
		(offeredsalary[i], maxjoboffer[i]) = [int(i) for i in input().split()]
	totalsalary = 0
	totalplaced = 0
	totalcompany = 0
	company = [0] * m
	for i in range(n):
		maxencounter = 0
		compi = -1
		qual = [int(i) for i in list(input())]
		for j in range(m):
			if qual[j] == 1:
				if offeredsalary[j] > maxencounter and offeredsalary[j] > minsalary[i]:
					if maxjoboffer[j] > 0:
						maxencounter = offeredsalary[j]
						compi = j
		if compi != -1:
			totalplaced += 1
			totalsalary += maxencounter
			maxjoboffer[compi] -= 1
			if company[compi] == 0:
				company[compi] = 1
				totalcompany += 1
	print(totalplaced, totalsalary, m - totalcompany, sep=' ')


class comp:
	maxsal = 0
	available = 0
	hired = 0
T = int(input())
for t in range(T):
	ls = list(map(int, input().split()))
	N = ls[0]
	M = ls[1]
	minsal = list(map(int, input().split()))
	co = []
	for O in range(M):
		obj = comp()
		p = list(map(int, input().split()))
		obj.maxsal = p[0]
		obj.available = p[1]
		obj.hired = 0
		co.append(obj)
	qual = [str(input()) for i in range(N)]
	result = []
	totalselected = 0
	totalsal = 0
	for i in range(N):
		S = qual[i]
		candidateselected = False
		for index in range(len(S)):
			if S[index] == '1' and minsal[i] <= co[index].maxsal and (co[index].available != 0):
				minsal[i] = co[index].maxsal
				hiringco = index
				candidateselected = True
		if candidateselected:
			co[hiringco].available = co[hiringco].available - 1
			co[hiringco].hired = 1
			totalselected = totalselected + 1
			totalsal = totalsal + co[hiringco].maxsal
	v = 0
	for m in co:
		if m.hired == 0:
			v = v + 1
	print(totalselected, totalsal, v)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	minSal = list(map(int, input().split()))
	info = list()
	selec = list()
	for _ in range(m):
		info.append(list(map(int, input().split())))
	for _ in range(n):
		selec.append(list(map(int, input())))
	cand = [0] * n
	sal = [0] * n
	comp = [0] * m
	for i in range(n):
		possible = list()
		possible = [ind for (ind, val) in enumerate(selec[i]) if val == 1]
		max_sal = -1
		max_com = -1
		for com in possible:
			if info[com][1] > 0 and info[com][0] > max_sal and (info[com][0] >= minSal[i]):
				max_sal = info[com][0]
				max_com = com
		if max_com > -1:
			cand[i] = 1
			sal[i] = max_sal
			comp[max_com] += 1
			info[max_com][1] -= 1
	print(sum(cand), sum(sal), comp.count(0))


t = int(input())
for testCase in range(t):
	(n, m) = map(int, input().split())
	minSalary = [int(x) for x in input().split()]
	offeredSalary = [0] * m
	maxJobOffers = [0] * m
	student = 0
	comp = -1
	salary = [0] * n
	isSelected = [0] * n
	recruitedOne = [0] * m
	qual = [[0 for x in range(m)] for y in range(n)]
	for i in range(1, m + 1):
		(offeredSalary[i - 1], maxJobOffers[i - 1]) = map(int, input().split())
	for i in range(1, n + 1):
		qual[i - 1] = input()
	for student in range(n):
		comp = -1
		for company in range(m):
			if qual[student][company] == '1' and maxJobOffers[company] > 0 and (offeredSalary[company] >= minSalary[student]) and (offeredSalary[company] > salary[student]):
				isSelected[student] = 1
				salary[student] = offeredSalary[company]
				comp = company
		if salary[student] > 0:
			maxJobOffers[comp] = maxJobOffers[comp] - 1
			recruitedOne[comp] = 1
	print(sum(isSelected), sum(salary), m - sum(recruitedOne))


def main():
	T = int(input())
	for t in range(T):
		(N, M) = input().split()
		N = int(N)
		M = int(M)
		min_salaries = input().split()
		for i in range(N):
			min_salaries[i] = int(min_salaries[i])
		offered_salary = []
		max_job_offers = []
		for i in range(M):
			lis = input().split()
			offered_salary.append(int(lis[0]))
			max_job_offers.append(int(lis[1]))
		qual = []
		for i in range(N):
			qual.append(input())
		number_hired_by_company = [0] * M
		total_salary_accepted = 0
		for s in range(N):
			max_salary = 0
			max_company = 0
			for c in range(M):
				if qual[s][c] == '0':
					continue
				elif number_hired_by_company[c] < max_job_offers[c]:
					if offered_salary[c] > max_salary:
						max_salary = offered_salary[c]
						max_company = c
			if max_salary == 0:
				continue
			elif max_salary >= min_salaries[s]:
				number_hired_by_company[max_company] += 1
				total_salary_accepted += max_salary
		number_jobbed_students = 0
		number_companies_didnt_hire = 0
		for n in number_hired_by_company:
			if n == 0:
				number_companies_didnt_hire += 1
			else:
				number_jobbed_students += n
		print(number_jobbed_students, total_salary_accepted, number_companies_didnt_hire)
main()


def main():
	T = int(input())
	for t in range(T):
		(N, M) = input().split()
		N = int(N)
		M = int(M)
		min_salaries = input().split()
		for i in range(N):
			min_salaries[i] = int(min_salaries[i])
		company_data = []
		for i in range(M):
			company_data.append(input().split())
			company_data[-1][0] = int(company_data[-1][0])
			company_data[-1][1] = int(company_data[-1][1])
		qual = []
		for i in range(N):
			qual.append(input())
		num_hired_by_company = [0] * M
		total_salary_accepted = 0
		for s in range(N):
			max_salary = 0
			max_company = 0
			for c in range(M):
				if qual[s][c] == '0':
					continue
				if company_data[c][0] > max_salary:
					if num_hired_by_company[c] < company_data[c][1]:
						max_salary = company_data[c][0]
						max_company = c
			if max_salary == 0:
				continue
			elif max_salary >= min_salaries[s]:
				num_hired_by_company[max_company] += 1
				total_salary_accepted += max_salary
		number_students_with_jobs = 0
		number_companies_didnt_hire = 0
		for n in num_hired_by_company:
			if n == 0:
				number_companies_didnt_hire += 1
			else:
				number_students_with_jobs += n
		print(number_students_with_jobs, total_salary_accepted, number_companies_didnt_hire, end='\n')
main()


t = int(input())
for i in range(t):
	f = input()
	f = list(map(int, f.split()))
	n = f[0]
	m = f[1]
	minsalary = input()
	b = []
	dup = []
	minsalary = list(map(int, minsalary.split()))
	for j in range(m):
		s = input()
		s = list(map(int, s.split()))
		b.append(list(s))
		dup.append(list(s))
	b.append([0, 0])
	qual = []
	for j in range(n):
		g = input()
		qual.append(g)
	count = 0
	salary = 0
	for j in range(n):
		maxi = -float('inf')
		h = m
		for k in range(m):
			if qual[j][k] == '1' and b[k][1] != 0 and (minsalary[j] <= b[k][0]):
				if b[k][0] > maxi:
					maxi = b[k][0]
					h = k
		b[h][1] = b[h][1] - 1
		if h != m:
			count = count + 1
			salary = salary + b[h][0]
	none = 0
	for j in range(m):
		if b[j][1] == dup[j][1]:
			none = none + 1
	print(count, salary, none)


Test = int(input())
while Test != 0:
	(N, M) = map(int, input().split())
	minSal = {}
	k = list(map(int, input().split()))
	for i in range(N):
		minSal.update({i: k[i]})
	CompDetail = {}
	for i in range(M):
		CompDetail.update({i: list(map(int, input().split()))})
	EmpComp = {}
	for i in range(N):
		EmpComp.update({i: list(input())})
	salarySum = 0
	HiringCompany = {}
	count0 = 0
	for i in minSal.keys():
		maxi = -1
		loc = -1
		for j in range(M):
			if EmpComp[i][j] == '1' and j in CompDetail.keys():
				if maxi < CompDetail[j][0]:
					maxi = CompDetail[j][0]
					loc = j
		if maxi >= minSal[i] and loc in CompDetail.keys():
			HiringCompany.update({loc: 1})
			count0 = count0 + 1
			CompDetail.update({loc: [CompDetail[loc][0], CompDetail[loc][1] - 1]})
			salarySum = salarySum + CompDetail[loc][0]
			if CompDetail[loc][1] == 0:
				del CompDetail[loc]
	print(count0, salarySum, M - len(HiringCompany.keys()))
	Test = Test - 1


Test = int(input())
while Test != 0:
	(N, M) = map(int, input().split())
	minSal = {}
	k = list(map(int, input().split()))
	for i in range(N):
		minSal.update({i: k[i]})
	CompDetail = {}
	for i in range(M):
		CompDetail.update({i: list(map(int, input().split()))})
	EmpComp = {}
	for i in range(N):
		EmpComp.update({i: list(input())})
	sum = 0
	salary = 0
	count0 = 0
	count1 = 0
	hey = {}
	for i in minSal.keys():
		maxi = -1
		loc = -1
		for j in range(M):
			if EmpComp[i][j] == '1' and j in CompDetail.keys():
				if maxi < CompDetail[j][0]:
					maxi = CompDetail[j][0]
					loc = j
		if maxi >= minSal[i] and loc in CompDetail.keys():
			hey.update({loc: 1})
			count0 = count0 + 1
			CompDetail.update({loc: [CompDetail[loc][0], CompDetail[loc][1] - 1]})
			sum = sum + CompDetail[loc][0]
			if CompDetail[loc][1] == 0:
				del CompDetail[loc]
	print(count0, sum, M - len(hey.keys()))
	Test = Test - 1


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	salary = 0
	candidates = 0
	companies = 0
	offeredSalary = []
	maxJobOffers = []
	for __ in range(M):
		(x, y) = map(int, input().split())
		offeredSalary.append(x)
		maxJobOffers.append(y)
	oldmaxjoboffers = maxJobOffers * 1
	for i in range(N):
		data = list(input())
		sal = minSalary[i]
		for j in range(len(data)):
			data[j] = int(data[j])
			if data[j] == 1:
				if sal <= offeredSalary[j] and maxJobOffers[j] > 0:
					sal = offeredSalary[j]
		for k in range(len(offeredSalary)):
			if sal == offeredSalary[k]:
				candidates = candidates + 1
				salary = salary + offeredSalary[k]
				maxJobOffers[k] = maxJobOffers[k] - 1
	for i in range(len(maxJobOffers)):
		if maxJobOffers[i] == oldmaxjoboffers[i]:
			companies += 1
	print(candidates, salary, companies)


for case in range(int(input())):
	(n, m) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	offer = []
	companyHappy = [False] * m
	candidateHappy = [False] * n
	for offered in range(m):
		offer.append(list(map(int, input().split())))
	qual = {}
	totalSalary = 0
	for candidate in range(n):
		qual[candidate] = input().strip()
	for candidate in qual.keys():
		cSalary = 0
		companyID = 0
		for company in range(m):
			if qual[candidate][company] == '1':
				if minSalary[candidate] <= offer[company][0] and offer[company][1] > 0:
					if cSalary < offer[company][0]:
						cSalary = offer[company][0]
						companyID = company
						candidateHappy[candidate] = True
		if candidateHappy[candidate]:
			offer[companyID][1] -= 1
			companyHappy[companyID] = True
			totalSalary += cSalary
	print(candidateHappy.count(True), totalSalary, companyHappy.count(False))


for t in range(int(input())):
	(N, M) = map(int, input().split())
	min_sal = list(map(int, input().split()))
	(off_sal, max_job) = ([None] * M, [None] * M)
	for i in range(M):
		(off_sal[i], max_job[i]) = map(int, input().split())
	max_job_copy = max_job[:]
	qual = [input().strip() for i in range(N)]
	happy = total = 0
	for i in range(N):
		choices = [(off_sal[j], j) for j in range(M) if qual[i][j] == '1' and off_sal[j] >= min_sal[i] and (max_job[j] > 0)]
		if choices:
			(max_sal, comp) = max(choices)
			happy += 1
			total += max_sal
			max_job[comp] -= 1
	sad = sum((m1 == m2 for (m1, m2) in zip(max_job, max_job_copy)))
	print(happy, total, sad)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	min = list(map(int, input().split()))
	salary = [0] * m
	emp = [0] * m
	for i in range(0, m):
		(salary[i], emp[i]) = map(int, input().split())
	qual = [0] * n
	for i in range(0, n):
		qual[i] = input()
	ca = w = count = s = su = 0
	f = [0] * 10000
	freq = [0] * 10000
	for i in range(0, n):
		max = 0
		for j in range(0, m):
			if qual[i][j] == '1':
				k = emp[j]
				if salary[j] > max and k != 0:
					max = salary[j]
		for j in range(0, m):
			if salary[j] == max and salary[j] >= min[i]:
				if emp[j] != 0:
					emp[j] = emp[j] - 1
					ca = ca + 1
					su = su + salary[j]
					f[w] = j
					freq[w] = -1
					w = w + 1
	for i in range(0, w):
		count = 1
		for j in range(i + 1, w):
			if f[i] == f[j]:
				count = count + 1
				freq[j] = 0
		if freq[i] != 0:
			freq[i] = count
	for i in range(0, w):
		if freq[i] != 0:
			s = s + 1
	print(ca, su, m - s)
	t = t - 1


import copy
t = int(input())
for i in range(0, t):
	job_offered = 0
	total_sal = 0
	comp_det = []
	cand_det = []
	num = [int(x) for x in input().split()]
	N = num[0]
	M = num[1]
	minSalary = [int(x) for x in input().split()]
	for j in range(0, M):
		comp_det.append([int(x) for x in input().split()])
	for k in range(0, N):
		x = input()
		cand = list(x)
		cand_det.append([int(s) for s in cand])
	comp_det_c = copy.deepcopy(comp_det)
	for l in range(0, N):
		salary = []
		for j in range(0, M):
			if cand_det[l][j] == 1 and comp_det[j][1] != 0:
				salary.append(comp_det[j][0])
			else:
				salary.append(0)
		if max(salary) >= minSalary[l]:
			job_offered = job_offered + 1
			total_sal = total_sal + max(salary)
			comp_det[salary.index(max(salary))][1] = comp_det[salary.index(max(salary))][1] - 1
	no_job = 0
	for l in range(0, M):
		if comp_det[l] == comp_det_c[l]:
			no_job = no_job + 1
	print(job_offered, total_sal, no_job)


def get_best_comp(cand_key, company):
	options = cand_key[1]
	index = -1
	val = -1
	for o in range(len(options)):
		if options[o] == '1':
			if company[o][1] > 0:
				if company[o][0] >= cand_key[0]:
					if company[o][0] > val:
						val = company[o][0]
						index = o
	if not index == -1:
		company[index][1] -= 1
	return val
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	minSalary = [int(x) for x in input().split()]
	comp = []
	for t in range(m):
		(sal, offer) = [int(x) for x in input().split()]
		comp.append([sal, offer, offer])
	cand = {}
	for t in range(n):
		temp = input()
		cand[t] = (minSalary[t], list(temp))
	jobs = salaries = nil_companies = 0
	for key in cand.keys():
		best_comp = get_best_comp(cand[key], comp)
		if not best_comp == -1:
			jobs += 1
			salaries += best_comp
	for elem in comp:
		if elem[1] - elem[2] == 0:
			nil_companies += 1
	print(jobs, salaries, nil_companies)


import math
import operator
for ii in range(int(input())):
	sal = 0
	count = 0
	comc = 0
	n = [int(x) for x in input().split()]
	minsal = [int(x) for x in input().split()]
	com = []
	for i in range(n[1]):
		a = [int(x) for x in input().split()]
		a.append(i)
		a.append(a[1])
		com.append(a)
	com.sort(key=operator.itemgetter(0), reverse=True)
	sel = []
	for i in range(n[0]):
		sel.append(input())
	for i in range(n[0]):
		for j in range(n[1]):
			if com[j][1] > 0 and com[j][0] >= minsal[i] and (sel[i][com[j][2]] == '1'):
				com[j][1] = com[j][1] - 1
				count = count + 1
				sal = sal + com[j][0]
				break
			elif minsal[i] > com[j][0]:
				break
	for i in range(n[1]):
		if com[i][3] == com[i][1]:
			comc = comc + 1
	print(count, sal, comc)


import math

def findalpha():
	data = [int(x) for x in input().split()]
	n = data[0]
	m = data[1]
	minSalary = [int(x) for x in input().split()]
	temp = []
	maxsal_maxjobs = []
	qual = []
	sumSalary = 0
	prev_offer = 0
	getsjobs = 0
	maxsal_maxjobs_temp = []
	for index in range(0, m):
		temp = []
		temp = [int(x) for x in input().split()]
		maxsal_maxjobs_temp.append(temp[1])
		maxsal_maxjobs.append(temp)
	for index in range(0, n):
		string_temp = input()
		qual.append(string_temp)
	for i in range(0, n):
		prev_offer = 0
		for j in range(0, m):
			if qual[i][j] == '1':
				if maxsal_maxjobs_temp[j] > 0 and maxsal_maxjobs[j][0] >= minSalary[i]:
					if maxsal_maxjobs[j][0] > prev_offer:
						prev_offer = maxsal_maxjobs[j][0]
						index_company = j
		if prev_offer > 0:
			getsjobs += 1
			sumSalary += prev_offer
			maxsal_maxjobs_temp[index_company] -= 1
	nojobs = 0
	for x in range(0, m):
		if maxsal_maxjobs[x][1] == maxsal_maxjobs_temp[x]:
			nojobs += 1
	print('%d %d %d' % (getsjobs, sumSalary, nojobs))
t = int(input())
while t > 0:
	t -= 1
	findalpha()


t = int(input())
for r in range(t):
	(n, m) = map(int, input().strip().split())
	minr = list(map(int, input().strip().split(' ')))
	osl = [0] * m
	mxin = [0] * m
	for i in range(m):
		(x, y) = map(int, input().strip().split(' '))
		osl[i] = x
		mxin[i] = y
	jb = [[0] * m for i in range(n)]
	for i in range(n):
		ip = input().strip()
		for j in range(m):
			jb[i][j] = int(ip[j])
	ofans = 0
	nr = set()
	nor = 0
	for j in range(m):
		nr.add(j)
	for i in range(n):
		maxof = 0
		tc = -1
		for j in range(m):
			if jb[i][j] == 1 and maxof < osl[j] and (mxin[j] > 0):
				maxof = osl[j]
				tc = j
		if minr[i] <= maxof:
			nor += 1
			ofans += maxof
			mxin[tc] -= 1
			if nr.__contains__(tc):
				nr.remove(tc)
	out = str(nor) + ' ' + str(ofans) + ' ' + str(len(nr))
	print(out)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	mim = list(map(int, input().split()))
	os = []
	mjo = []
	qual = []
	l = []
	z = -1
	s1 = 0
	s2 = 0
	s3 = 0
	c = 0
	for j in range(m):
		(y, z) = map(int, input().split())
		os.append(y)
		mjo.append(z)
		l.append(0)
	for j in range(n):
		b = list(input())
		qual.append(b)
		b = []
	z = -1
	for j in range(n):
		c = 0
		for k in range(m):
			if l[k] < mjo[k]:
				if qual[j][k] == '1':
					if os[k] >= mim[j] and os[k] > c:
						c = os[k]
						z = k
		if z != -1:
			l[z] += 1
			z = -1
	for j in range(m):
		if l[j] > 0:
			s1 = s1 + l[j]
			s2 = s2 + l[j] * os[j]
		else:
			s3 = s3 + 1
	print(s1, s2, s3, sep=' ')


import sys
n = int(input().strip())
for i in range(0, n):
	a = [int(scores_temp) for scores_temp in input().strip().split(' ')]
	b = [int(scores_temp) for scores_temp in input().strip().split(' ')]
	js = [[]] * a[1]
	company = [0] * a[1]
	mtr = [[]] * a[0]
	ans1 = ans2 = 0
	ans3 = a[1]
	for i in range(0, a[1]):
		js[i] = [int(scores_temp) for scores_temp in input().strip().split(' ')]
	for i in range(0, a[0]):
		mtr[i] = list(input().strip())
		t = count = 0
		salary = 0
		for j in range(0, a[1]):
			if mtr[i][j] == '1':
				minsal = b[i]
				saloff = js[j][0]
				if saloff >= minsal and salary < saloff and (js[j][1] > 0):
					salary = saloff
					t = j
					count = 1
		if count == 1:
			js[t][1] = js[t][1] - 1
			ans1 = ans1 + 1
			company[t] = 1
			ans2 = ans2 + salary
	print(ans1, ans2, a[1] - sum(company))


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	offeredSalary = []
	maxJobOffers = []
	for _ in range(M):
		(offeredSalary_item, maxJobOffers_item) = map(int, input().split())
		offeredSalary.append(offeredSalary_item)
		maxJobOffers.append(maxJobOffers_item)
	qual = []
	for i in range(N):
		qual_item = str(input())
		if i == 0:
			qual = [list(map(str, qual_item.split()))]
		else:
			qual.append(list(map(str, qual_item.split())))
	maxJobOffers2 = []
	for item in maxJobOffers:
		maxJobOffers2.append(item)
	count_candidates_successful = 0
	count_not_comp = 0
	count_sal = 0
	comP_old = []
	comP_new = []
	for x in range(M):
		comP_old.append(N)
		comP_new.append(N)
	for i in range(N):
		flag = 0
		qualified_i = []
		for j in range(M):
			if qual[i][0][j] == '1':
				qualified_i.append(j)
		maximum_offsal = -1
		if qualified_i != []:
			maximum_offsal = minSalary[i]
			for item in qualified_i:
				if maximum_offsal <= offeredSalary[item] and maxJobOffers2[item] > 0:
					maximum_offsal = offeredSalary[item]
					flag = 1
			if flag == 1:
				count_sal += maximum_offsal
				count_candidates_successful += 1
				index = offeredSalary.index(maximum_offsal)
				maxJobOffers2[index] -= 1
	for (index, item) in enumerate(maxJobOffers2):
		if item == maxJobOffers[index]:
			count_not_comp += 1
	print(str(count_candidates_successful) + ' ' + str(count_sal) + ' ' + str(count_not_comp))


class Company:

	def __init__(self, offeredSalary, maxJobOffers, index, hiredAny=False, sortedIndex=None):
		self.offeredSalary = offeredSalary
		self.maxJobOffers = maxJobOffers
		self.index = index
		self.hiredAny = hiredAny
		self.sortedIndex = sortedIndex
output = []
T = int(input())
for t in range(0, T):
	(N, M) = map(int, input().split(' '))
	minSalary = list(map(int, input().split(' ')))
	companies = []
	for ctr in range(0, M):
		(offSal, maxJobOff) = map(int, input().split(' '))
		companies.append(Company(offeredSalary=offSal, maxJobOffers=maxJobOff, index=ctr))
	companies.sort(key=lambda x: x.offeredSalary, reverse=True)
	for ctr in range(0, M):
		companies[ctr].sortedIndex = ctr
	num_placed_candidates = 0
	total_salary = 0
	for candidate in range(0, N):
		qual = list(map(int, list(input())))
		relevantCompanies = [company for company in companies if qual[company.index] == 1]
		for c in relevantCompanies:
			if c.maxJobOffers > 0:
				if c.offeredSalary >= minSalary[candidate]:
					companies[c.sortedIndex].maxJobOffers -= 1
					num_placed_candidates += 1
					total_salary += c.offeredSalary
					companies[c.sortedIndex].hiredAny = True
					break
				else:
					break
	output.append([num_placed_candidates, total_salary, len([company for company in companies if company.hiredAny == False])])
for t in range(0, T):
	print(*output[t])


t = int(input())
for pq in range(t):
	t1 = list(map(int, input().split()))
	n = t1[0]
	m = t1[1]
	minSal = [int(x) for x in input().split()]
	comp = []
	qual = []
	visLis = []
	totSal = 0
	gotJob = 0
	for i in range(m):
		comp.append([int(x) for x in input().split()])
	for i in range(n):
		qual.append([int(x) for x in list(input())])
	for i in range(n):
		sal = 0
		ind = -1
		for j in range(m):
			if qual[i][j] == 1:
				if minSal[i] < comp[j][0] and comp[j][0] > sal and (comp[j][1] != 0):
					sal = comp[j][0]
					ind = j
		if ind != -1:
			comp[ind][1] -= 1
			if ind not in visLis:
				visLis.append(ind)
			gotJob += 1
			totSal += sal
	print(gotJob, totSal, m - len(visLis))


for _ in range(int(input())):
	(n1, m1) = input().split()
	(n1, m1) = (int(n1), int(m1))
	minisal = []
	minisal = list(map(int, input().split()))
	givensal = []
	joboff = []
	st = [0] * m1
	for j in range(m1):
		(h1, h2) = input().split()
		(h1, h2) = (int(h1), int(h2))
		givensal.append(h1)
		joboff.append(h2)
	qualdarr = []
	for u in range(n1):
		o = list(input())
		qualdarr.append(o)
	ans1 = 0
	ans2 = 0
	for i in range(n1):
		expect = int(minisal[i])
		total1 = 0
		status = 0
		for j in range(m1):
			if int(qualdarr[i][j]) == 1 and expect <= givensal[j] and (joboff[j] != 0):
				total1 = max(givensal[j], total1)
		if total1 != 0:
			ans1 += 1
			ans2 += total1
			st[givensal.index(total1)] = 1
			joboff[givensal.index(total1)] -= 1
	ans3 = 0
	for i in range(m1):
		if st[i] == 0:
			ans3 += 1
	print(ans1, ans2, ans3)


def getkey(item):
	return item[0]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	expected_salary = list(map(int, input().split()))
	salary_offered = []
	qual = []
	i = 0
	companies = [0] * m
	salary_got = 0
	job_got = 0
	while i < m:
		(offered_Salary, max_job) = map(int, input().split())
		salary_offered.append([offered_Salary, max_job, i])
		i += 1
	i = 0
	while i < n:
		max = pos = 0
		qual = input()
		for j in range(m):
			if qual[j] == '1' and salary_offered[j][0] >= expected_salary[i] and (salary_offered[j][1] > 0):
				if max < salary_offered[j][0]:
					max = salary_offered[j][0]
					pos = j
		if max > 0:
			salary_offered[pos][1] -= 1
			salary_got += max
			companies[pos] = 1
			job_got += 1
		i += 1
	print(job_got, salary_got, companies.count(0))


t = int(input())
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	minsal = list(map(int, input().split()))
	m1 = m
	n1 = n
	offsal = []
	maxjob = []
	offmax = []
	offmax = []
	che = [0] * m
	for i in range(m):
		(a, b) = map(int, input().split())
		offsal.append(a)
		maxjob.append(b)
		offmax.append([a, b])
	offmax.sort(reverse=True)
	qual = []
	while n1:
		n1 -= 1
		a = list(input())
		qual.append(a)
	total = 0
	noof = 0
	noofcomp = m
	for i in range(n):
		exp = int(minsal[i])
		st = 0
		total1 = 0
		for j in range(m):
			if int(qual[i][j]) == 1 and exp <= offsal[j]:
				if maxjob[j] != 0:
					total1 = max(total1, offsal[j])
		if total1 != 0:
			noof += 1
			che[offsal.index(total1)] = 1
			maxjob[offsal.index(total1)] -= 1
			total += total1
	print(noof, total, che.count(0))


import numpy as np
tc = int(input())
while tc:
	(n, m) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	offeredSalary = np.zeros(m)
	maxJobOffers = np.zeros(m)
	for i in range(m):
		(offeredSalary[i], maxJobOffers[i]) = map(int, input().split())
	qual = []
	for j in range(n):
		qual.append(list(input()))
	a = np.argsort(offeredSalary)
	a = a[::-1]
	minSalary = np.array(minSalary)
	ncand = 0
	tsal = 0
	com = [0] * m
	for j in range(n):
		for i in a:
			if '1' == qual[j][i]:
				if maxJobOffers[i] > 0 and offeredSalary[i] >= minSalary[j]:
					com[i] = 1
					tsal += offeredSalary[i]
					ncand += 1
					maxJobOffers[i] -= 1
					break
	print(ncand, int(tsal), com.count(0))
	tc -= 1


def gcac(minsal, offsal, maxJoboff, qual, n, m):
	total = []
	count = [1] * n
	flag = [0] * m
	offers = []
	cand = []
	mjo = []
	mjo[:] = maxJoboff
	fl = 0
	for j in range(n):
		c = 0
		sal = 0
		comp = -1
		flag = 0
		for k in range(m):
			if qual[j][k] == '1' and maxJoboff[k] > 0 and (minsal[j] <= offsal[k]):
				offers.append([offsal[k], k])
				c += 1
				flag = 1
				if sal < offsal[k]:
					sal = offsal[k]
					comp = k
		if flag == 1:
			cand.append([sal, comp])
			maxJoboff[comp] -= 1
			fl += 1
	(total, nt) = (0, 0)
	for r in range(fl):
		if cand[r][0] != 0:
			total += cand[r][0]
	for u in range(m):
		if mjo[u] == maxJoboff[u]:
			nt += 1
	if n >= 1 and m >= 1 and (m <= 1000) and (m <= 1000) and (t <= 10) and (t >= 1):
		print(fl, total, nt)
	return 0
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().strip().split(' '))
	minsal = list(map(int, input().strip().split(' ')))
	(offsal, maxJoboff, qual) = ([], [], [])
	a = []
	for k in range(m):
		(o, mj) = map(int, input().strip().split(' '))
		offsal.append(o)
		maxJoboff.append(mj)
	for j in range(n):
		qual.append(input())
	gcac(minsal, offsal, maxJoboff, qual, n, m)


t = int(input())
for index in range(t):
	inp = input().split()
	n = int(inp[0])
	m = int(inp[1])
	minSalary = [int(x) for x in input().split()]
	offeredSalary = []
	maxJobOffers = []
	qual = []
	noOfJobs = 0
	totalSalary = 0
	noJobOfferCompanies = [1 for x in range(m)]
	for index2 in range(m):
		(sal, offers) = input().split()
		(sal, offers) = (int(sal), int(offers))
		offeredSalary.append(sal)
		maxJobOffers.append(offers)
	for index2 in range(n):
		arr = [int(x) for x in list(input())]
		qual.append(arr)
	for i in range(n):
		for j in range(m):
			qual[i][j] = qual[i][j] * offeredSalary[j]
	for i in range(n):
		maxSal = max(qual[i])
		maxSalCompany = qual[i].index(maxSal)
		if maxSal >= minSalary[i] and maxJobOffers[maxSalCompany] > 0:
			noOfJobs += 1
			noJobOfferCompanies[maxSalCompany] = 0
			totalSalary += maxSal
			maxJobOffers[maxSalCompany] -= 1
			if maxJobOffers[maxSalCompany] == 0:
				for index2 in range(n):
					qual[index2][maxSalCompany] = 0
	print(noOfJobs, totalSalary, sum(noJobOfferCompanies))


def main():
	tests = int(input())
	for t in range(tests):
		(n, m) = [int(x) for x in input().split()]
		minSal = [int(x) for x in input().split()]
		offeredSal = []
		jobCount = []
		companyWorth = [0] * m
		for i in range(m):
			(a, b) = [int(x) for x in input().split()]
			offeredSal.append(a)
			jobCount.append(b)
		candPlaced = 0
		totalSalary = 0
		compNoCand = m
		for cand in range(n):
			jobOffered = list(input())
			maxOffer = 0
			maxComp = -1
			for comp in range(m):
				if jobOffered[comp] == '1' and offeredSal[comp] > maxOffer and (minSal[cand] <= offeredSal[comp]) and (jobCount[comp] > 0):
					maxOffer = offeredSal[comp]
					maxComp = comp
			if maxComp != -1:
				jobCount[maxComp] -= 1
				totalSalary += maxOffer
				candPlaced += 1
				compNoCand -= 1 if companyWorth[maxComp] == 0 else 0
				companyWorth[maxComp] = 1
		print(candPlaced, totalSalary, compNoCand)
main()


test = int(input())
for n in range(test):
	(N, M) = input().split()
	minS = list(map(int, input().split()))
	(info, qual) = ([], [])
	for j in range(int(M)):
		tab = list(map(int, input().split()))
		info.append(tab)
	for k in range(int(N)):
		qualval = input()
		qual.append(qualval)
	(numcand, total, entrp) = (0, 0, 0)
	while entrp < int(M):
		nbrCand = 0
		big = max(info)
		if big[0] > 0:
			bigIndex = info.index(big)
			for i in range(int(N)):
				if minS[i] != -1 and qual[i][bigIndex] == '1' and (big[1] > 0) and (minS[i] <= big[0]):
					nbrCand = nbrCand + 1
					numcand = numcand + 1
					minS[i] = -1
					big[1] = big[1] - 1
				if big[1] == 0:
					break
			total = total + nbrCand * big[0]
			if nbrCand != 0:
				info[bigIndex] = [-1, -1]
			else:
				info[bigIndex] = [-2, -2]
		else:
			break
		if numcand == int(N):
			break
		entrp = entrp + 1
	Emptyentrp = info.count([-2, -2])
	print(numcand, total, Emptyentrp)


salaire_min = []
max_job = []
salaire_fixe = []
qual = []

def fonction(n, m):
	candidats_retenus = 0
	montant_total = 0
	entse_zero_emp = set(range(m))
	entse_poss = []
	deja_recru = [0] * m
	for i in range(n):
		entse_poss.append([])
	for i in range(n):
		for j in range(m):
			if qual[i][j] == '1':
				entse_poss[i].append(j)
	for student in range(n):
		max_sal = salaire_min[student]
		choix = -1
		for entse in entse_poss[student]:
			if deja_recru[entse] < max_job[entse] and salaire_fixe[entse] >= max_sal:
				max_sal = salaire_fixe[entse]
				choix = entse
		if choix >= 0:
			deja_recru[choix] += 1
			candidats_retenus += 1
			montant_total += max_sal
			entse_zero_emp -= {choix}
	return (candidats_retenus, montant_total, len(entse_zero_emp))
T = int(input())
for a in range(T):
	(N, M) = (int(i) for i in input().split())
	salaire_min = [int(i) for i in input().split()]
	max_job = []
	salaire_fixe = []
	for j in range(M):
		(x, y) = (int(i) for i in input().split())
		salaire_fixe.append(x)
		max_job.append(y)
	qual = []
	for i in range(N):
		qual.append(input())
	(a, b, c) = fonction(N, M)
	print(a, b, c)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	minSal = list(map(int, input().split()))
	maxSal = []
	jobAvail = []
	finaljob = []
	for i in range(m):
		(a, b) = map(int, input().split())
		maxSal.append([a, b, i])
		finaljob.append(0)
	availabejobs = sum(jobAvail)
	sal = 0
	maxSal.sort(key=lambda x: x[0], reverse=True)
	alloted = [[] for i in range(m)]
	for i in range(n):
		sel = input()
		for (ind, c) in enumerate(sel):
			if c == '1':
				alloted[ind].append(True)
			else:
				alloted[ind].append(False)
	sal = 0
	stplaced = 0
	for i in range(n):
		for (ind, tp) in enumerate(maxSal):
			if alloted[tp[2]][i] and tp[0] >= minSal[i] and (tp[1] > 0):
				sal += tp[0]
				stplaced += 1
				maxSal[ind][1] -= 1
				if finaljob[ind] == 0:
					finaljob[ind] = 1
				break
	print(stplaced, sal, m - sum(finaljob))
	t -= 1


t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	mnsl = list(map(int, input().split()))
	ar1 = []
	ar2 = []
	for i in range(m):
		(ofs, mxjb) = map(int, input().split())
		ar1.append(ofs)
		ar2.append(mxjb)
	ar3 = []
	for i in ar2:
		ar3.append(i)
	tt = 0
	nt = m
	jb = 0
	for i in range(n):
		opt = list(input())
		sal = mnsl[i]
		k = -1
		ln = len(opt)
		for j in range(ln):
			if opt[j] == '1':
				if ar1[j] > sal and ar2[j] > 0:
					sal = ar1[j]
					k = j
		if k != -1:
			tt += sal
			jb += 1
			ar2[k] -= 1
	for i in range(m):
		if ar2[i] != ar3[i]:
			nt -= 1
	print(jb, tt, nt)


t = int(input())
for i in range(t):
	minsal = list()
	salary = list()
	jobs = list()
	qualify = list()
	count1 = list()
	salary1 = []
	count = countstud = max = sum = x = 0
	k = input().split()
	n = int(k[0])
	m = int(k[1])
	minsal = list(map(int, input().split()))
	for j in range(0, m):
		val = input().split()
		salary.append(int(val[0]))
		jobs.append(int(val[1]))
	for j in range(0, m):
		count1.append(0)
	for j in range(n):
		qualify.append(input())
	for j in range(0, n):
		max = flag = c = 0
		for k in range(0, m):
			flag = 0
			if qualify[j][k] == '1' and minsal[j] <= salary[k] and (count1[k] < jobs[k]):
				if max < salary[k]:
					pos = k
					max = salary[k]
					c = 1
		if c == 1:
			sum = sum + max
			countstud = countstud + 1
			count1[pos] = count1[pos] + 1
	for k in range(m):
		if count1[k] == 0:
			x = x + 1
	print(str(countstud) + ' ' + str(sum) + ' ' + str(x))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	total = 0
	os = list()
	limit = list()
	h = list()
	minsal = list(map(int, input().split()))
	for j in range(m):
		(o, l) = map(int, input().split())
		os.append(o)
		limit.append(l)
	qual = [[0 for x in range(m)] for y in range(n)]
	for j in range(n):
		qual[j] = input()
	for j in range(m):
		h.append(0)
	for j in range(n):
		big = 0
		c = -1
		for k in range(m):
			if qual[j][k] == '1':
				if h[k] < limit[k]:
					if minsal[j] <= os[k]:
						if big < os[k]:
							big = os[k]
							c = k
		if c != -1:
			total = total + big
			h[c] = h[c] + 1
	print(sum(h), end=' ')
	print(total, end=' ')
	print(h.count(0))


for test in range(int(input())):
	(n, m) = list(map(int, input().split()))
	stud = list(map(int, input().split()))
	comp = [list(map(int, input().split())) for i in range(m)]
	selection = [input() for i in range(n)]
	stud = list(zip(stud, selection))
	for i in range(m):
		comp[i].append(i)
	comp.sort(reverse=True, key=lambda s: s[0])
	placed = int()
	tot_sal = int()
	comp_y = []
	for i in stud:
		if set(i[1]) == {0}:
			continue
		else:
			for j in comp:
				if i[1][j[2]] == '1' and j[0] >= i[0]:
					placed += 1
					tot_sal += j[0]
					j[1] -= 1
					if j[1] == 0:
						comp.remove(j)
					comp_y.append(j[0])
					break
	print(placed, tot_sal, m - len(set(comp_y)))


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	minSalary = [int(x) for x in input().split()]
	offeredSalary = [1 for k in range(M)]
	maxJobOffers = [1 for k in range(M)]
	for j in range(M):
		(offeredSalary[j], maxJobOffers[j]) = map(int, input().split())
	qual = [[0 for k in range(M)] for j in range(N)]
	for j in range(N):
		x = input()
		qual[j] = list(x)
		qual[j] = [int(y) for y in qual[j]]
	(c, sal, comp) = (0, 0, 0)
	m = [0 for k in range(M)]
	last = [0 for k in range(N)]
	for j in range(N):
		for k in range(M):
			if qual[j][k] == 1 and m[k] < maxJobOffers[k] and (offeredSalary[k] >= minSalary[j]):
				if last[j] < offeredSalary[k]:
					last[j] = offeredSalary[k]
					a = k
		if last[j] != 0:
			c += 1
			m[a] += 1
		sal += last[j]
	comp = m.count(0)
	print(c, sal, comp)


for t in range(int(input())):
	(N, M) = map(int, input().split())
	n = list(map(int, input().split()))
	m = [[i for i in list(map(int, input().split()))] for j in range(M)]
	qual = []
	for a in range(N):
		qual.append(input())
	s = [0] * M
	c = 0
	sum = 0
	for d in range(N):
		ex = n[d]
		x = 0
		w = qual[d]
		for f in range(M):
			if w[f] == '1':
				if x <= m[f][0] and m[f][1] > 0:
					x = m[f][0]
		for h in range(M):
			if x == m[h][0] and x >= ex:
				sum = sum + x
				s[h] = s[h] + 1
				m[h][1] = m[h][1] - 1
				c = c + 1
	print(c, sum, s.count(0))


def ni():
	s = input()
	while len(s) == 0:
		s = input()
	try:
		return int(s)
	except:
		return 0

def nia():
	s = input()
	while len(s) == 0:
		s = input()
	s = s.split()
	iVal = []
	for i in range(len(s)):
		iVal.append(int(s[i]))
	return iVal

class HiringMatch:

	def __init__(self):
		self.minSalary = []
		self.offeredSalary = []
		self.maxJobs = []
		self.offers = []
		self.N = 0
		self.M = 0

	def test1(self):
		self.minSalary = [5000, 10000, 3000, 20, 100]
		self.offeredSalary = [10000, 800, 600, 10, 1000, 2000]
		self.maxJobs = [2, 2, 1, 8, 9, 10]
		self.offers = ['111111', '100000', '000000', '000001', '100100']
		self.N = 5
		self.M = 6
		self.solve()

	def solve(self):
		accepted = [0] * self.M
		totalS = 0
		numAccepted = 0
		for i in range(self.N):
			bestoffer = -1
			for j in range(self.M):
				if self.offers[i][j] == '0':
					continue
				elif self.offeredSalary[j] < self.minSalary[i]:
					continue
				elif self.maxJobs[j] == accepted[j]:
					continue
				if bestoffer < 0:
					bestoffer = j
				elif self.offeredSalary[j] > self.offeredSalary[bestoffer]:
					bestoffer = j
			if bestoffer >= 0:
				numAccepted += 1
				totalS += self.offeredSalary[bestoffer]
				accepted[bestoffer] += 1
		noHire = 0
		for i in range(self.M):
			if accepted[i] == 0:
				noHire += 1
		print('{0} {1} {2}'.format(numAccepted, totalS, noHire))

	def read(self):
		NM = nia()
		self.N = NM[0]
		self.M = NM[1]
		self.minSalary = nia()
		for i in range(self.M):
			s = nia()
			self.offeredSalary.append(s[0])
			self.maxJobs.append(s[1])
		self.offers = [''] * self.N
		for i in range(self.N):
			self.offers[i] = input()

def main():
	T = ni()
	for t in range(T):
		hiring = HiringMatch()
		hiring.read()
		hiring.solve()
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	company = []
	cama = []
	for i in range(m):
		a = list(map(int, input().split()))
		company.append(a)
		cama.append(tuple(a))
	qual = []
	can = 0
	sal = 0
	com = m
	for i in range(n):
		inp = input()
		ma = 0
		f1 = 0
		k = 100000
		for j in range(m):
			if inp[j] == '1' and minSalary[i] <= company[j][0] and (company[j][1] > 0):
				f1 = 1
				if ma < company[j][0]:
					k = j
					ma = company[j][0]
		if k != 100000:
			company[k][1] -= 1
		sal += ma
		if f1:
			can += 1
	for i in range(m):
		if cama[i][1] != company[i][1]:
			com -= 1
	print(can, sal, com)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	minSalary = []
	offeredSalary = [0] * m
	maxJobOffers = [0] * m
	totalSalary = 0
	countStudent = 0
	countCompany = 0
	minSalary = list(map(int, input().split()))
	for i in range(0, m):
		(offeredSalary[i], maxJobOffers[i]) = map(int, input().split())
	companyRecruit = [0] * m
	for i in range(n):
		job = input()
		tempPackage = 0
		tempCompany = -1
		for j in range(0, m):
			if job[j] == '1' and offeredSalary[j] >= minSalary[i] and (maxJobOffers[j] > 0) and (tempPackage < offeredSalary[j]):
				tempPackage = offeredSalary[j]
				tempCompany = j
		if tempCompany != -1:
			if companyRecruit[tempCompany] == 0:
				countCompany += 1
			companyRecruit[tempCompany] = 1
			maxJobOffers[tempCompany] -= 1
			countStudent += 1
			totalSalary += offeredSalary[tempCompany]
	print(countStudent, ' ', totalSalary, ' ', m - countCompany)


n = int(input())
for d in range(0, n, 1):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	matrix = []
	for i in range(0, a[1], 1):
		p = list(map(int, input().split()))
		matrix.append(p)
	y = []
	for i in range(0, a[1], 1):
		y.append(matrix[i][1])
	comp = []
	for i in range(0, a[0], 1):
		l = input()
		comp.append(l)
	flag = 0
	count = 0
	cmp = 0
	for i in range(0, a[0], 1):
		t = 0
		for j in range(0, a[1], 1):
			if comp[i][j] == '1':
				if matrix[j][0] > b[i] and matrix[j][1] > 0:
					if matrix[j][0] > t and t == 0:
						t = matrix[j][0]
						x = j
						flag = flag + 1
						count = count + t
						matrix[j][1] = matrix[j][1] - 1
					elif matrix[j][0] > t and t != 0:
						count = count - t + matrix[j][0]
						matrix[x][1] = matrix[x][1] + 1
						matrix[j][1] = matrix[j][1] - 1
						x = j
						t = matrix[j][0]
	w = 0
	for i in range(0, a[1], 1):
		if y[i] > matrix[i][1]:
			w = w + 1
	print(flag, count, a[1] - w)


t = int(input())
for q in range(t):
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	li2 = []
	for i in range(m):
		(a, b) = map(int, input().split())
		lix = []
		lix.append(a)
		lix.append(b)
		li2.append(lix)
	lif = []
	for i in range(n):
		z = input()
		z = list(z)
		z = list(map(int, z))
		lif.append(z)
	lis = [0] * n
	lic = [0] * m
	ans = 0
	for i in range(0, n):
		ma = 0
		pos = 0
		pp = 0
		for j in range(0, m):
			if lif[i][j] == 1:
				if li2[j][0] > ma and li2[j][0] >= li[i] and (li2[j][1] > 0):
					ma = li2[j][0]
		for k in range(0, m):
			if li2[k][0] == ma and li2[k][0] >= li[i] and (li2[k][1] > 0):
				li2[k][1] = li2[k][1] - 1
				ans = ans + li2[k][0]
				lis[i] = 1
				lic[k] = 1
				pos = k
				break
	print(lis.count(1), ans, lic.count(0))


t = int(input())

def key_offered_salary(comp):
	return comp[1]
for _ in range(0, t):
	(n, m) = [int(i) for i in input().split(' ')]
	min_salary_arr = [int(i) for i in input().split(' ')]
	companies = [None] * m
	for comp_idx in range(0, m):
		(offered_salary, max_job_offers) = [int(i) for i in input().split(' ')]
		companies[comp_idx] = (comp_idx, offered_salary, max_job_offers, [])
	companies = sorted(companies, reverse=True, key=key_offered_salary)
	comp_lookup = [None] * len(companies)
	for (idx, comp) in enumerate(companies):
		comp_lookup[idx] = comp[0]
	jobs_obtained = 0
	total_salary = 0
	total_empty_companies = 0
	for cand_idx in range(0, n):
		quals = input()
		quals = [quals[c] for c in comp_lookup]
		for (comp_idx, qual) in enumerate(quals):
			if qual == '1' and companies[comp_idx][1] > min_salary_arr[cand_idx] and (len(companies[comp_idx][3]) < companies[comp_idx][2]):
				companies[comp_idx][3].append(cand_idx)
				jobs_obtained += 1
				total_salary += companies[comp_idx][1]
				break
	for comp in companies:
		if len(comp[3]) == 0:
			total_empty_companies += 1
	print('{} {} {}'.format(jobs_obtained, total_salary, total_empty_companies))


t = int(input())
for test in range(t):
	(n, m) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	offeredSalary = []
	maxJobOffers = []
	for i in range(m):
		(x, y) = map(int, input().split())
		offeredSalary.append(x)
		maxJobOffers.append(y)
	qual = []
	for i in range(n):
		qual.append(input())
	numJobs = 0
	salary = 0
	gotJob = [0] * m
	for i in range(n):
		maxSal = 0
		company = -1
		for j in range(m):
			if qual[i][j] == '1' and maxJobOffers[j] > 0:
				if offeredSalary[j] >= minSalary[i]:
					if maxSal < offeredSalary[j]:
						maxSal = offeredSalary[j]
						company = j
		if maxSal != 0:
			gotJob[company] = 1
			numJobs += 1
			maxJobOffers[company] -= 1
			salary += maxSal
	print(numJobs, salary, m - sum(gotJob))


import random
debug = False
test = False
if test is True:
	T = 10
else:
	T = int(input())
for _ in range(T):
	if test is True:
		print('Generating...')
		N = 1000
		M = 1000
		minSalary = []
		offeredSalary = set()
		qual = []
		maxJobOffers = []
		for _ in range(N):
			minSalary.append(random.randrange(1000000000))
			tmp = ''
			for _ in range(M):
				tmp += str(random.randrange(2))
			qual.append(tmp)
		for _ in range(M):
			maxJobOffers.append(1 + random.randrange(1000000))
		while len(offeredSalary) < M:
			offeredSalary.add(1 + random.randrange(1000000000))
		offeredSalary = list(offeredSalary)
		print('...done')
	else:
		s = input()
		(N, M) = [int(c) for c in s.strip().split()]
		s = input()
		minSalary = [int(c) for c in s.strip().split()]
		offeredSalary = []
		maxJobOffers = []
		for _ in range(M):
			s = input()
			tmp = [int(c) for c in s.strip().split()]
			offeredSalary.append(tmp[0])
			maxJobOffers.append(tmp[1])
		qual = []
		for _ in range(N):
			s = input()
			a = s.strip()
			qual.append(a)
	if debug is True:
		print(N, M)
		print(minSalary)
		print(offeredSalary)
		print(maxJobOffers)
		print(qual)
	jobFound = 0
	totalSalary = 0
	companyFound = [0] * M
	for n in range(N):
		jobOffer = qual[n]
		maxSal = -1
		comp = -1
		for (c, job) in enumerate(jobOffer):
			if job == '1' and offeredSalary[c] >= minSalary[n] and (maxJobOffers[c] > 0):
				if offeredSalary[c] > maxSal:
					maxSal = offeredSalary[c]
					comp = c
		if comp == -1:
			pass
		else:
			maxJobOffers[comp] -= 1
			companyFound[comp] = 1
			totalSalary += offeredSalary[comp]
			jobFound += 1
	print(jobFound, totalSalary, M - sum(companyFound))


def solve(N, M, minSalary, offeredSalary, maxJobOffers, qual):
	potentialCompaniesForStudents = []
	for i in range(N):
		companiesForStudent = []
		potentialCompaniesForStudents.append(companiesForStudent)
		for j in range(M):
			if qual[i][j] == '1' and offeredSalary[j] >= minSalary[i]:
				companiesForStudent.append(j)
	count_of_candidates_that_get_the_job = 0
	total_amount_of_salaries = 0
	count_of_companies_that_didnt_hire = 0
	availableJobOffers = maxJobOffers[:]
	for i in range(N):
		companiesForStudent = potentialCompaniesForStudents[i]
		companiesForStudent.sort(key=lambda idx: offeredSalary[idx])
		for company_index in reversed(companiesForStudent):
			if availableJobOffers[company_index] > 0:
				count_of_candidates_that_get_the_job += 1
				total_amount_of_salaries += offeredSalary[company_index]
				availableJobOffers[company_index] -= 1
				break
	for pair in zip(maxJobOffers, availableJobOffers):
		if pair[0] == pair[1]:
			count_of_companies_that_didnt_hire += 1
	return (count_of_candidates_that_get_the_job, total_amount_of_salaries, count_of_companies_that_didnt_hire)
T = int(input())
for t in range(T):
	(N, M) = (int(i) for i in input().split())
	minSalary = [int(i) for i in input().split()]
	offeredSalary = []
	maxJobOffers = []
	for m in range(M):
		(s, j) = (int(i) for i in input().split())
		offeredSalary.append(s)
		maxJobOffers.append(j)
	qual = []
	for n in range(N):
		qual.append(input())
	(count_of_candidates_that_get_the_job, total_amount_of_salaries, count_of_companies_that_didnt_hire) = solve(N, M, minSalary, offeredSalary, maxJobOffers, qual)
	print(count_of_candidates_that_get_the_job, total_amount_of_salaries, count_of_companies_that_didnt_hire)


for _ in range(int(input())):
	(n, m) = [int(e) for e in input().split(' ')]
	a = [int(e) for e in input().split(' ')]
	b = []
	c = []
	d = []
	for i in range(m):
		(x, y) = [int(e) for e in input().split(' ')]
		b.append(x)
		c.append(y)
	g = c[:]
	for i in range(n):
		x = [int(e) for e in input()]
		d.append(x)
	ans = 0
	ans1 = 0
	ans2 = 0
	for i in range(n):
		z = -1
		w = -1
		for j in range(m):
			if d[i][j] == 1 and b[j] > a[i] and (b[j] > z) and (c[j] > 0):
				z = b[j]
				w = j
		if w != -1:
			c[w] -= 1
			ans += 1
		if z != -1:
			ans1 += z
	for i in range(m):
		if c[i] == g[i]:
			ans2 += 1
	print(ans, ans1, ans2)


for case in range(int(input())):
	ans = [0, 0]
	(n, m) = tuple(map(int, input().split(' ')))
	minSalary = list(map(int, input().split(' ')))
	(offeredSalary, maxJobOffers) = ([], [])
	na = set([x for x in range(m)])
	for _ in range(m):
		(q, w) = tuple(map(int, input().split(' ')))
		offeredSalary.append(q)
		maxJobOffers.append(w)
	qual = []
	for _ in range(n):
		qual.append(list(input()))
	for i in range(n):
		(high, c) = (-1, -1)
		for j in range(m):
			if qual[i][j] == '1' and maxJobOffers[j] and (offeredSalary[j] >= minSalary[i]):
				if offeredSalary[j] > high:
					high = offeredSalary[j]
					c = j
		if c > -1:
			ans[0] += 1
			ans[1] += offeredSalary[c]
			na.discard(c)
			maxJobOffers[c] -= 1
	print(ans[0], ans[1], len(na))


T = int(input())
for i in range(0, T):
	first = input()
	first = first.split()
	N = int(first[0])
	M = int(first[1])
	minSalary = input()
	minSalary = minSalary.split()
	offeredSalary = []
	maxJobOffers = []
	for j in range(0, M):
		second = input()
		second = second.split()
		offeredSalary.append(int(second[0]))
		maxJobOffers.append(int(second[1]))
	maxJobOffers2 = []
	maxJobOffers2 = maxJobOffers[:]
	qual = []
	for j in range(0, N):
		third = input()
		qual.append([])
		qual[j] = third
	total_cand = N
	total_sal = 0
	total_comp = 0
	for j in range(0, N):
		flag = -1
		temp_salary = 0
		for k in range(0, M):
			if qual[j][k] == '1' and offeredSalary[k] > int(minSalary[j]) and (maxJobOffers[k] > 0) and (offeredSalary[k] > temp_salary):
				flag = k
				temp_salary = offeredSalary[k]
		if flag == -1:
			total_cand -= 1
		else:
			maxJobOffers[flag] -= 1
			total_sal += temp_salary
	for j in range(0, M):
		if maxJobOffers2[j] == maxJobOffers[j]:
			total_comp += 1
	print(total_cand, ' ', total_sal, ' ', total_comp)


t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	min_s = list(map(int, input().split()))
	off_s = []
	max_j = []
	for j in range(0, m):
		(f, g) = map(int, input().split())
		off_s.append(f)
		max_j.append(g)
	qual = []
	for j in range(0, n):
		qual.append(list(map(int, input())))
	jobs = [0] * m
	total_s = 0
	for j in range(0, n):
		flag_s = 0
		flag_i = -1
		for k in range(0, m):
			if qual[j][k] == 1 and min_s[j] <= off_s[k] and (jobs[k] < max_j[k]) and (flag_s < off_s[k]):
				flag_s = off_s[k]
				flag_i = k
		if flag_i != -1:
			jobs[flag_i] += 1
			total_s += flag_s
	print(sum(jobs), total_s, jobs.count(0))


t = int(input())
saljob = []
qual = []
job = []
booloffer = []
while t > 0:
	mn = [int(x) for x in input().split()]
	minSalary = [int(x) for x in input().split()]
	for i in range(0, mn[1]):
		temp = [int(x) for x in input().split()]
		saljob.insert(len(saljob), temp)
	for i in range(0, mn[0]):
		qual.insert(len(qual), input())
	for i in range(0, mn[0]):
		job.insert(len(job), -1)
	for i in range(0, mn[1]):
		booloffer.insert(len(booloffer), False)
	for i in range(0, mn[0]):
		index = -1
		maxsal = minSalary[i]
		for j in range(0, mn[1]):
			if qual[i][j] == '1' and saljob[j][0] >= maxsal and (saljob[j][1] > 0):
				index = j
				maxsal = saljob[j][0]
		if index > -1:
			saljob[index][1] = saljob[index][1] - 1
			booloffer[index] = True
			job[i] = index
	salary = 0
	count = 0
	for i in range(0, mn[0]):
		if job[i] >= 0:
			salary = salary + saljob[job[i]][0]
			count = count + 1
	nooffer = 0
	for i in range(0, mn[1]):
		if booloffer[i] == False:
			nooffer = nooffer + 1
	print(count, end=' ')
	print(salary, end=' ')
	print(nooffer)
	saljob.clear()
	booloffer.clear()
	qual.clear()
	job.clear()
	t = t - 1


t = int(input())
while t > 0:
	t = t - 1
	count = 0
	total = 0
	offer = 0
	offeredSalary = []
	maxJobOffer = []
	new = []
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	salary = list(map(int, input().split()))
	for i in range(m):
		(x, y) = input().split()
		(x, y) = (int(x), int(y))
		offeredSalary.append(x)
		maxJobOffer.append(y)
		new.append(y)
	for i in range(n):
		result = 0
		a = list(input())
		for j in range(len(a)):
			if a[j] == '1':
				if salary[i] <= offeredSalary[j] and maxJobOffer[j] > 0:
					result = max(result, offeredSalary[j])
		for j in range(m):
			if offeredSalary[j] == result:
				total = total + result
				maxJobOffer[j] = maxJobOffer[j] - 1
				count = count + 1
	for i in range(len(new)):
		if new[i] == maxJobOffer[i]:
			offer = offer + 1
	print(count, total, offer)


def func():
	(n, m) = list(map(int, input().split()))
	minsal = list(map(int, input().split()))
	offsal = []
	maxjoboff = []
	for i in range(m):
		(a, b) = list(map(int, input().split()))
		offsal.append(a)
		maxjoboff.append(b)
	qual = []
	ans1 = 0
	ans2 = 0
	ans3 = [False for i in range(m)]
	for i in range(n):
		qual.append(list(input()))
		temp_max = 0
		pos = -1
		for j in range(len(qual[i])):
			if qual[i][j] == '1':
				if maxjoboff[j] > 0 and offsal[j] > temp_max and (offsal[j] >= minsal[i]):
					temp_max = offsal[j]
					pos = j
		if pos != -1:
			maxjoboff[pos] -= 1
			ans3[pos] = True
			ans2 += offsal[pos]
			ans1 += 1
	ans3c = 0
	for i in range(len(ans3)):
		if ans3[i] == False:
			ans3c += 1
	print(ans1, ans2, ans3c)
t = int(input())
while t > 0:
	t -= 1
	func()


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	min_Salary = list(map(int, input().split()))
	Company_offer = []
	for i in range(m):
		(x, y) = map(int, input().split())
		Company_offer.append([x, y, 0])
	selection = []
	for i in range(n):
		s = input()
		selection.append(s)
	co = 0
	total_salary = 0
	for i in range(n):
		k = -1
		sal = min_Salary[i]
		for j in range(m):
			if selection[i][j] == '1':
				if Company_offer[j][0] >= sal and Company_offer[j][1] > 0:
					sal = Company_offer[j][0]
					k = j
		if k != -1:
			co += 1
			Company_offer[k][1] -= 1
			Company_offer[k][2] = 1
			total_salary += Company_offer[k][0]
	comp = 0
	for i in range(m):
		if Company_offer[i][2] == 0:
			comp += 1
	print(co, total_salary, comp)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	min_salary = []
	min_salary = list(map(int, input().split()))
	row = []
	amount = 0
	count = 0
	sum = 0
	column = []
	offerd_salary = []
	max_joboffer = []
	for i in range(m):
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		offerd_salary.append(a)
		max_joboffer.append(b)
	new_max_joboffers = max_joboffer * 1
	for i in range(n):
		x = input()
		row = list(x)
		salary_get = min_salary[i]
		for j in range(len(row)):
			row[j] = int(row[j])
			if row[j] == 1:
				if salary_get <= offerd_salary[j] and max_joboffer[j] > 0:
					salary_get = offerd_salary[j]
		for k in range(len(offerd_salary)):
			if salary_get == offerd_salary[k]:
				count = count + 1
				amount = amount + offerd_salary[k]
				max_joboffer[k] = max_joboffer[k] - 1
	for i in range(len(max_joboffer)):
		if max_joboffer[i] == new_max_joboffers[i]:
			sum = sum + 1
	print(count, amount, sum)


t = int(input())
for i in range(t):
	(n, m) = [int(s) for s in input().split()]
	salary = [int(s) for s in input().split()]
	a = []
	for i in range(m):
		(p, q) = [int(s) for s in input().split()]
		a.append([p, q])
	qual = [[0 for i in range(m)] for j in range(n)]
	for i in range(n):
		qual[i] = input()
	company = [0] * m
	total = 0
	students = 0
	for i in range(n):
		sal = salary[i]
		maxi = -1
		temp_max = -1
		for j in range(m):
			if qual[i][j] == '1' and a[j][1] > 0 and (a[j][0] > sal) and (maxi < a[j][0]):
				maxi = a[j][0]
				temp_max = j
		if temp_max != -1:
			a[temp_max][1] -= 1
			students += 1
			total += maxi
			company[temp_max] = 1
	print('%s %s %s' % (students, total, m - company.count(1)))


t = int(input())
while t:
	t -= 1
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	minSalary = list(map(int, input().split()))
	company = [[0 for x in range(2)] for y in range(m)]
	for i in range(m):
		(company[i][0], company[i][1]) = input().split()
		(company[i][0], company[i][1]) = [int(company[i][0]), int(company[i][1])]
	companyTaken = [0 for x in range(m)]
	students = 0
	tsal = 0
	for i in range(n):
		s = input()
		comp = -1
		sal = -1
		for j in range(len(s)):
			if s[j] == '1' and company[j][0] >= minSalary[i] and (company[j][1] > 0) and (sal <= company[j][0]):
				comp = j
				sal = company[j][0]
		if sal > -1:
			students += 1
			tsal += sal
			company[comp][1] -= 1
			companyTaken[comp] = 1
	notTaken = 0
	for i in companyTaken:
		if i == 0:
			notTaken += 1
	print(str(students) + ' ' + str(tsal) + ' ' + str(notTaken))


import copy
answers = []
g = int(input())
for i in range(g):
	k = 0
	s = 0
	d = 0
	(n, m) = list(map(int, input().split()))
	minSalary = list(map(int, input().split()))
	offeredSalaries = []
	jobsAvail = []
	for i in range(m):
		t = input().split()
		offeredSalaries.append(int(t[0]))
		jobsAvail.append(int(t[1]))
	q = copy.copy(jobsAvail)
	arr = []
	for i in range(n):
		arr.append(list(map(int, ' '.join(input().split()))))
	for i in range(n):
		minSal = minSalary[i]
		ar = arr[i]
		probJobsIndex = []
		probJobsSalaries = []
		for l in range(m):
			if ar[l] == 1:
				if jobsAvail[l] > 0:
					if offeredSalaries[l] > minSal:
						probJobsSalaries.append(int(offeredSalaries[l]))
						probJobsIndex.append(int(l))
		if len(probJobsSalaries) == 0:
			continue
		else:
			salary = max(probJobsSalaries)
			salary_index = offeredSalaries.index(salary)
			k += 1
			s += salary
			jobsAvail[salary_index] -= 1
	for (a, b) in zip(jobsAvail, q):
		if a == b:
			d += 1
	answers.append([k, s, d])
for i in answers:
	print(*i)


test = int(input())
for t in range(test):
	(n, m) = [int(i) for i in input().split()]
	minSalary = [int(i) for i in input().split()]
	ncad = 0
	tsal = 0
	company = {}
	for c in range(m):
		(os, mjo) = [int(i) for i in input().split()]
		company[c] = [os, mjo, 0]
	for wc in range(n):
		student = input()
		mySal = minSalary[wc]
		maxOffer = 0
		selComp = None
		for (s, v) in enumerate(student):
			if v == '1':
				if company[s][1] > 0:
					offer_sal = company[s][0]
					if offer_sal >= mySal and offer_sal >= maxOffer:
						maxOffer = offer_sal
						selComp = s
		if selComp is not None:
			company[selComp][2] = 1
			company[selComp][1] += -1
		if maxOffer > 0:
			ncad += 1
			tsal += maxOffer
	ncomp = len([k for (k, v) in company.items() if company[k][2] == 0])
	print(ncad, tsal, ncomp)


from sys import stdin
t = int(stdin.readline())
while t:
	t -= 1
	(n, m) = map(int, stdin.readline().split())
	minsalary = list(map(int, stdin.readline().split()))
	offer = []
	for i in range(m):
		offer.append(tuple(map(int, stdin.readline().split())))
	qual = []
	for i in range(n):
		qual.append(stdin.readline())
	total_salaries = 0
	get_job = 0
	no_cand = set([x for x in range(m)])
	for i in range(n):
		maxsal = 0
		comp = -1
		for j in range(m):
			if qual[i][j] == '1':
				if offer[j][0] >= minsalary[i] and offer[j][0] > maxsal and (offer[j][1] > 0):
					maxsal = offer[j][0]
					comp = j
		if maxsal != 0:
			total_salaries += maxsal
			offer[comp] = (offer[comp][0], offer[comp][1] - 1)
			get_job += 1
			if comp in no_cand:
				no_cand.remove(comp)
	print(get_job, total_salaries, len(no_cand))


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	minsalary = list(map(int, input().split()))
	offer = []
	for i in range(m):
		offer.append(tuple(map(int, input().split())))
	qual = []
	for i in range(n):
		qual.append(input())
	total_salaries = 0
	get_job = 0
	no_cand = set([x for x in range(m)])
	for i in range(n):
		maxsal = 0
		comp = -1
		for j in range(m):
			if qual[i][j] == '1':
				if offer[j][0] >= minsalary[i] and offer[j][0] > maxsal and (offer[j][1] > 0):
					maxsal = offer[j][0]
					comp = j
		if maxsal != 0:
			total_salaries += maxsal
			offer[comp] = (offer[comp][0], offer[comp][1] - 1)
			get_job += 1
			if comp in no_cand:
				no_cand.remove(comp)
	print(get_job, total_salaries, len(no_cand))


T = int(input())
for t in range(T):
	(N, M) = [int(i) for i in input().split()]
	minSalary = [int(i) for i in input().split()]
	Offer = dict()
	for i in range(M):
		Offer[i] = [int(_) for _ in input().split()]
	num_candidate = 0
	company = set()
	total_salary = 0
	for i in range(N):
		qual = input()
		tmp_index = []
		max_index = []
		tmp_len = 0
		for j in range(M):
			if qual[j] == '1' and Offer[j][1] > 0 and (Offer[j][0] >= minSalary[i]):
				tmp_index.append(j)
				max_index.append(Offer[j][0])
				tmp_len += 1
		if tmp_len > 0:
			m = max(max_index)
			m_index = [p for p in range(tmp_len) if max_index[p] == m][0]
			company_chosen = tmp_index[m_index]
			Offer[company_chosen][1] -= 1
			num_candidate += 1
			company.add(company_chosen)
			total_salary += m
	print(num_candidate, total_salary, M - len(company))


t = int(input())
for k in range(t):
	(n, m) = map(int, input().split())
	minsalary = []
	minsalary = list(map(int, input().split()))
	offeredsalary = []
	maxjoboffers = []
	flag = 0
	salary = 0
	for v in range(m):
		(s, d) = map(int, input().split())
		offeredsalary.append(s)
		maxjoboffers.append(d)
	lis = []
	for g in range(m):
		lis.append(1)
	for i in range(n):
		qual = []
		qual = list(input())
		g = 0
		maximum = 0
		for j in range(len(qual)):
			if qual[j] == '1' and maxjoboffers[j] > 0 and (offeredsalary[j] > minsalary[i]):
				if maximum < offeredsalary[j]:
					g = 1
					maximum = offeredsalary[j]
			if maximum != 0 and j == len(qual) - 1:
				h = offeredsalary.index(maximum)
				lis[h] = lis[h] - 1
				maxjoboffers[h] = maxjoboffers[h] - 1
		if g == 1:
			flag += 1
		salary += maximum
	print('{} {} {}'.format(flag, salary, lis.count(1)))


test = int(input())
for i in range(test):
	offered_salary = []
	total_job = []
	placed = []
	sum = 0
	(n, m) = map(int, input().split())
	count1 = 0
	count2 = m
	min_salary = list(map(int, input().split()))
	for j in range(m):
		(a, b) = map(int, input().split())
		offered_salary.append(a)
		total_job.append(b)
	no_job = list(total_job)
	for j in range(n):
		placed.append(input())
	for j in range(n):
		get = 0
		maxi = []
		for k in range(m):
			if int(placed[j][k]) == 1 and offered_salary[k] >= min_salary[j] and (total_job[k] > 0):
				maxi.append(k)
				get += 1
		if get > 0:
			great = offered_salary[maxi[0]]
			change_post = offered_salary.index(offered_salary[maxi[0]])
			for l in maxi:
				if offered_salary[l] > great:
					great = offered_salary[l]
					change_post = l
			total_job[change_post] -= 1
			sum += great
			count1 += 1
	for j in range(m):
		if no_job[j] != total_job[j]:
			count2 -= 1
	print(count1, sum, count2)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	minSalary = list(map(int, input().split()))
	offeredSalary = []
	maxJobOffers = []
	for i in range(m):
		(a, b) = map(int, input().split())
		offeredSalary.append(a)
		maxJobOffers.append(b)
	maxJobOffersCopy = list(maxJobOffers)
	qual = []
	for i in range(n):
		qual.append(list(map(int, input())))
	candidateNumber = 0
	candidateGotJob = 0
	total = 0
	for i in qual:
		companyNumber = 0
		gotJob = False
		salary = minSalary[candidateNumber]
		gotJobByCompany = 0
		for j in i:
			if j == 1 and maxJobOffers[companyNumber] > 0 and (salary <= offeredSalary[companyNumber]):
				salary = offeredSalary[companyNumber]
				gotJob = True
				gotJobByCompany = companyNumber
			companyNumber += 1
		if gotJob:
			maxJobOffers[gotJobByCompany] -= 1
			candidateGotJob += 1
			total += salary
		candidateNumber += 1
	sadCompany = 0
	for i in range(len(maxJobOffers)):
		if maxJobOffers[i] == maxJobOffersCopy[i]:
			sadCompany += 1
	print(candidateGotJob, total, sadCompany, '\n')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ips = input()
	minsalary = [0] * n
	i = 0
	for token in ips.split():
		minsalary[i] = int(token)
		i += 1
	company = [[i, 0, 0] for i in range(m)]
	for i in range(m):
		(company[i][1], company[i][2]) = map(int, input().split())
	qual = [0] * n
	for i in range(n):
		qual[i] = input()
	empavail = [1] * n
	company = sorted(company, key=lambda x: x[1], reverse=True)
	(withjob, totalsalary, sadcompany) = (0, 0, 0)
	for ele in company:
		count = ele[2]
		for j in range(n):
			cond1 = int(qual[j][ele[0]]) and empavail[j]
			if cond1:
				cond2 = minsalary[j] <= ele[1]
				if cond2:
					count -= 1
					withjob += 1
					empavail[j] = 0
					totalsalary += ele[1]
					if count == 0:
						break
		if count == ele[2]:
			sadcompany += 1
	print(withjob, totalsalary, sadcompany)


T = int(input().strip())
for _ in range(T):
	(N, M) = input().strip().split(' ')
	(N, M) = [int(N), int(M)]
	minSalary = [0] + list(map(int, input().strip().split(' ')))
	(offeredSalary, maxJobOffers) = ([0] * (M + 1), [0] * (M + 1))
	for i in range(1, M + 1):
		(offeredSalary[i], maxJobOffers[i]) = input().strip().split(' ')
		(offeredSalary[i], maxJobOffers[i]) = [int(offeredSalary[i]), int(maxJobOffers[i])]
	qual = [0] * (N + 1)
	for i in range(1, N + 1):
		qual[i] = [0] + list(map(int, input().strip()))
	JobGot = [0] * (M + 1)
	li = []
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if qual[i][j] == 1 and JobGot[j] < maxJobOffers[j] and (minSalary[i] <= offeredSalary[j]):
				li.append(offeredSalary[j])
		if len(li) != 0:
			JobGot[offeredSalary.index(max(li))] += 1
		li.clear()
	candidate_count = 0
	amount = 0
	choker = 0
	for i in range(1, M + 1):
		if JobGot[i] == 0:
			choker += 1
		if JobGot[i] > 0:
			candidate_count += JobGot[i]
			amount = amount + offeredSalary[i] * JobGot[i]
	print(candidate_count, amount, choker, sep=' ')


import copy
T = int(input().strip())
while T:
	(N, M) = map(int, input().strip().split())
	mSal = list(map(int, input().strip().split()))
	cp = []
	for i in range(M):
		cp.append(list(map(int, input().strip().split())))
	cp1 = copy.deepcopy(cp)
	cd = []
	for i in range(N):
		cd.append(input().strip())
	(g, s, c) = (0, 0, 0)
	for i in range(len(cd)):
		m = -1
		cs = -1
		for j in range(len(cd[i])):
			if cd[i][j] == '1':
				if mSal[i] <= cp[j][0] and cp[j][1] and (m < cp[j][0]):
					m = cp[j][0]
					cs = j
		if cs != -1:
			cp[cs][1] -= 1
			g += 1
			s += cp[cs][0]
	for i in range(len(cp)):
		if cp[i][1] == cp1[i][1]:
			c += 1
	print(g, s, c)
	T -= 1