Read problems statements in [Hindi], [Mandarin Chinese], [Vietnamese], and [Bengali] as well.

There are $K$ problems in a contest with $N$ participants. All the problems don't necessarily have the same points assigned to them - you are given an array $A$ of integers, where $A_{i}$ denotes the points assigned to the $i^{th}$ problem. If a participant solves the $i^{th}$ problem, they will get $A_{i}$ points added to their total score. Note that there are no partial points - they can get only $0$ or $A_{i}$ points on the $i^{th}$ problem. For each participant $i$, you are also given their final verdict in each problem in the form of a binary string $S_{i}$ - a $1$ denotes that they solved that problem, and a $0$ denotes that they did not. 

Your job is to find the total score of each participant.

------ Input: ------

The first line of input contains a single integer $T$, denoting the number of testcases. Then the testcases follow. 
First line of each testcase contains $2$ space separated integers, $N$ and $K$, denoting the number of participants and the number of problems in the contest respectively.
The second line contains $K$ space separated integers - $A_{1}, A_{2}, \ldots, A_{K}$, where $A_{i}$ denotes the points assigned to the $i^{th}$  problem.
The $i^{th}$ of the next $N$ lines contains a binary string $S_{i}$ of length $K$, where $S_{ij}$ represents the verdict of the $j^{th}$ problem for $i^{th}$ participant. $S_{ij} = 1$ if they solved that problem, and $S_{ij} = 0$ otherwise.

------ Output: ------
For each testcase, output $N$ lines, with the $i^{th}$ line containing a single integer denoting the total score of the $i^{th}$ participant.

------ Constraints  ------
$1 ≤ T ≤ 5$
$1 ≤ A_{i} ≤ 10^{5}$
$0 ≤ S_{ij} ≤ 1$
Sum of $N * K$ over all tests is atmost $10^{6}$
$1 ≤ N, K$

----- Sample Input 1 ------ 
3
2 2
1 2
01
10
2 2
1 2
11
00
2 1
100
0
1
----- Sample Output 1 ------ 
2
1
3
0
0
100
----- explanation 1 ------ 
Case 1: The first participant's binary string is "$01$", which means that they did not solve the first problem, but they solved the second problem. And as the points assigned to the two problems are $1$ and $2$, the total score of the first participant is $2$. Hence the first output is $2$.

Similarly, the second participant's binary string is "$10$", which means that they solved the first problem, but did not solve the second problem. So their total score is $1$. Hence the second output is $1$.

Case 2: The first participant's binary string is "$11$", which means that they solved both the first and second problems. And as the points assigned to the two problems are $1$ and $2$, the total score of the first participant is $1 + 2 = 3$. Hence the third output is $3$.

Similarly, the second participant's binary string is "$00$", which means that they did not solve any problem. So their total score is $0$. And hence the fourth output is $0$.

Case 3: The first participant's binary string is "$0$", which means that they did not solve the only problem of the contest. Hence the total score of the first participant is $0$. Hence the fifth output is $0$.

Similarly, the second participant's binary string is "$1$", which means that they solved the only problem in the contest. And as the points assigned to that problem is $100$, the total score of the second participant is $100$. Hence the last output is $100$.

Difficulty: MEDIUM
Tags: Mathematics

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = [int(i) for i in input().split()]
	for i in range(n):
		s = input()
		ans = 0
		for j in range(k):
			if s[j] == '1':
				ans += p[j]
		print(ans)


for _ in range(int(input())):
	(mrs, prblm) = map(int, input().split())
	point = list(map(int, input().split()))
	for i in range(mrs):
		solved = input()
		score = 0
		for i in range(prblm):
			if solved[i] == '1':
				score += point[i]
		print(score)


t = int(input())
for t in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	for j in range(n):
		s = input()
		sum = 0
		for i in range(k):
			if s[i] == '1':
				sum += arr[i]
		print(sum)


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	s = input().split()
	for i in range(n):
		tot = 0
		s1 = input()
		for j in range(k):
			if s1[j] == '1':
				tot = tot + int(s[j])
		print(tot)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	x = [int(x) for x in input().split()]
	y = []
	for i in range(n):
		j = input()
		y.append(j)
	z = []
	for i in range(n):
		s = 0
		for j in range(k):
			if y[i][j] == '1':
				s += x[j]
		z.append(s)
	for i in z:
		print(i)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	for i in range(N):
		s = input()
		count = 0
		for j in range(len(s)):
			if s[j] == '1':
				count += A[j]
		print(count)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	S = []
	for i in range(N):
		S = input()
		tot = 0
		for j in range(K):
			if S[j] == '1':
				tot += A[j]
		print(tot)


t = input()
for c in range(0, int(t)):
	(n, k) = input().split()
	a = input().split()
	for x in range(0, int(n)):
		s = input()
		total = 0
		for y in range(0, int(k)):
			if s[y] == '1':
				total = total + int(a[y])
		print(total)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	marks_for_kprob = list(map(int, input().split()))
	a = []
	for i in range(n):
		s = input()
		a.append(s)
	for i in range(n):
		total = 0
		for j in range(k):
			if a[i][j] == '1':
				total += marks_for_kprob[j]
		print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		score = 0
		s = input()
		for j in range(k):
			if s[j] == '1':
				score += a[j]
		print(score)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	for j in range(x):
		b = input()
		count = 0
		for k in range(len(b)):
			if b[k] == '1':
				count += a[k]
		print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	s = []
	for i in range(n):
		p = input()
		s.append(p)
	new = []
	for i in range(n):
		mark1 = 0
		for j in range(k):
			mark2 = int(s[i][j]) * a[j]
			mark1 += mark2
		new.append(mark1)
	for elem in new:
		print(elem)


n = int(input())
for i in range(n):
	(N, K) = map(int, input().split(' '))
	score = list(map(int, input().split(' ')))
	for j in range(N):
		s = str(input())
		total = 0
		for k in range(K):
			if s[k] == '1':
				total += score[k]
		print(total)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for j in range(n):
		st = input()
		for p in range(k):
			ans = ans + arr[p] * int(st[p])
		print(ans)
		ans = 0


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for j in range(n):
		cur = 0
		p = input()
		for i in range(len(p)):
			if p[i] == '1':
				cur += a[i]
		print(cur)


def solve(n, k, ques, ans):
	res = 0
	for i in range(len(ans)):
		if ans[i] == '1':
			res += ques[i]
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	marks = [int(j) for j in input().split()]
	arr = []
	for i in range(n):
		ans = input()
		print(solve(n, k, marks, ans))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list((int(ele) for ele in input().strip().split()))[:k]
	for i in range(n):
		s = input()
		t = 0
		for i in range(k):
			if s[i] == '1':
				t += a[i]
		print(t)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	Score_list = list(map(int, input().split()))
	P_list = []
	for _ in range(n):
		P_list.append(input())
	for each in P_list:
		total_score = 0
		for i in range(len(each)):
			if int(each[i]) == 1:
				total_score += Score_list[i]
		print(total_score)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = list(map(int, input().split()))
	for i in range(x):
		s = input()
		c = 0
		for i in range(y):
			c += int(s[i]) * z[i]
		print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	A = list(map(int, input().split()))
	for j in range(a):
		s1 = str(input())
		c = 0
		for i in range(b):
			c += int(s1[i]) * int(A[i])
		print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	marks = [int(x) for x in input().split()]
	for i in range(n):
		score = 0
		inp = input()
		list1 = []
		for i in inp:
			list1.append(int(i))
		for j in range(len(list1)):
			score += list1[j] * marks[j]
		print(score)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	li = [int(i) for i in input().split()]
	for i in range(n):
		total = 0
		string = input()
		for j in range(k):
			if string[j] == '1':
				total += li[j]
			else:
				continue
		print(total)
	t -= 1


for _ in range(int(input())):
	(memb_n, prob_n) = map(int, input().split())
	points_li = list(map(int, input().split()))
	for _ in range(memb_n):
		prob_li = input()
		ans = 0
		for (i, j) in enumerate(prob_li):
			if j == '1':
				ans += points_li[i]
		print(ans)


for num in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		s = input()
		g = 0
		for j in range(k):
			if s[j] == '0':
				continue
			else:
				g += a[j]
		print(f'{g}')


for i in range(int(input())):
	(N, K) = map(int, input().split())
	Points = list(map(int, input().split()))
	for k in range(N):
		ParticipantSol = input()
		ParticipantSol = [*ParticipantSol]
		ParticipantSol = [int(i) for i in ParticipantSol]
		Score = 0
		for j in range(K):
			if ParticipantSol[j] == 1:
				Score += Points[j]
		print(Score)


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	for j in range(n):
		string = input()
		ans = 0
		for k in range(len(string)):
			if string[k] == '1':
				ans += arr[k]
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	for j in range(n):
		sum = 0
		s = str(input())
		bi = []
		bi[0:] = s
		for z in range(k):
			if bi[z] == '1':
				sum = sum + a[z]
		print(sum)


t = int(input())
for i in range(t):
	(cand, prob) = map(int, input().split())
	marks = list(map(int, input().split()))
	for p in range(cand):
		st = input()
		score = 0
		for q in range(prob):
			score = score + int(st[q]) * marks[q]
		print(score)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	for j in range(n):
		st1 = input()
		z = 0
		sum1 = 0
		for l in st1:
			sum1 += int(l) * list1[z]
			z += 1
		print(sum1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	for j in range(n):
		s = input()
		ans = 0
		for a in range(k):
			ans += int(s[a]) * l1[a]
		print(ans)


testCases = int(input())
for testCase in range(testCases):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for _ in range(n):
		bs = str(input())
		p = 0
		for i in range(k):
			if bs[i] == '1':
				p += a[i]
		print(p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	marks = list(map(int, input().split()))
	students = list()
	for i in range(n):
		students.append(input())
	for i in students:
		total = 0
		for j in range(k):
			if i[j] == '1':
				total += marks[j]
		print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		l = input()
		score = [int(l[i]) * a[i] for i in range(k)]
		print(sum(score))


for x in range(int(input())):
	(n, k) = [int(d) for d in input().split()]
	a = [int(d) for d in input().split()]
	for i in range(n):
		s = input()
		score = 0
		for j in range(len(s)):
			if s[j] == '1':
				score += a[j]
		print(score)


t = int(input())
l = []
points = []
for i in range(t):
	l = input().split(' ')
	n = int(l[0])
	points = input().split(' ')
	for x in range(n):
		sum = 0
		a = input()
		p = 0
		for x in a:
			sum = sum + int(x) * int(points[p])
			p = p + 1
		print(sum)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for l in range(n):
		s = list(input())
		sum = 0
		for m in range(len(s)):
			if s[m] == '1':
				sum += a[m]
		print(sum)


for _ in range(int(input())):
	N = int(input().split()[0])
	A = [int(s) for s in input().split()]
	for _ in range(N):
		print(sum((a * (b == '1') for (a, b) in zip(A, input()))))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	for j in range(n):
		sum = 0
		s = input()
		for l in range(k):
			sum = sum + a[l] * int(s[l])
		print(sum)


q = int(input())
while q > 0:
	q -= 1
	(x, y) = list(map(int, input().split()))
	z = list(map(int, input().split()))
	for i in range(1, x + 1):
		str = input()
		total = 0
		for j in range(0, len(str)):
			if str[j] == '0':
				continue
			else:
				total += z[j]
		print(total)


t = int(input())
for k in range(t):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	for i in range(a):
		e = 0
		d = str(input())
		for j in range(b):
			if d[j] == '1':
				e += c[j]
		print(e)


t = int(input())
while t > 0:
	(N, K) = [int(x) for x in input().split()]
	points = [int(x) for x in input().split()]
	while N > 0:
		count = 0
		score = input()
		for i in range(len(score)):
			if score[i] == '1':
				count += points[i]
		print(count)
		N -= 1
	t -= 1


for x in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for xx in range(n):
		s = list(map(int, list(input())))
		ans = 0
		for xxx in range(k):
			ans += a[xxx] * s[xxx]
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	Ai = list(map(int, input().split()))[:k]
	for i in range(n):
		sume = 0
		si = input()
		for i in range(k):
			sume += int(si[i]) * Ai[i]
		print(sume)


T = int(input())
for i in range(0, T):
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	A = input().split()
	for j in range(0, K):
		A[j] = int(A[j])
	for j in range(0, N):
		b = input()
		b = list(b)
		sums = 0
		for k in range(0, K):
			sums += int(b[k]) * A[k]
		print(sums)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().lstrip().split()))
	for i in range(n):
		s = list(input())
		sum = 0
		for j in range(len(s)):
			if s[j] == '1':
				sum += arr[j]
		print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(n):
		sc = 0
		s = input()
		for j in range(len(s)):
			sc += int(s[j]) * arr[j]
		print(sc)


def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	(N, K) = inparr()
	arr = inparr()
	varr = []
	scarr = []
	for i in range(N):
		varr.append(input())
	for i in varr:
		tmps = 0
		for j in range(K):
			if int(i[j]):
				tmps += arr[j]
		scarr.append(tmps)
	for i in scarr:
		print(i)


for jj in range(int(input())):
	(n, k) = map(int, input().split())
	marks = list(map(int, input().split()))
	qs = []
	for i in range(n):
		qs.append(list(map(int, input())))
	for i in qs:
		s = 0
		for j in range(k):
			s += i[j] * marks[j]
		print(s)


try:
	t = int(input())
	for i in range(t):
		(n, k) = list(map(int, input().split()))
		mark = list(map(int, input().split()))
		for i in range(n):
			obtain = input()
			sum = 0
			for j in range(len(obtain)):
				if obtain[j] == '1':
					sum = sum + mark[j]
			print(sum)
except:
	pass


try:
	test = int(input())
	for i in range(test):
		(n, k) = list(map(int, input().split()))
		m = list(map(int, input().split()))
		for _ in range(n):
			ans = input()
			total = 0
			for t in range(len(ans)):
				if ans[t] == '1':
					total += m[t]
			print(total)
except:
	pass


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	for i in range(n):
		s = input()
		sc = 0
		for j in range(k):
			if s[j] == '1':
				sc += p[j]
		print(sc)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	total = 0
	score = list(map(int, input().split()))
	for i in range(0, n):
		total = 0
		b = input()
		s = list(b)
		for i in range(len(s)):
			if s[i] == '1':
				total = total + score[i]
		print(total)


import sys
input = sys.stdin.readline

def rii():
	return range(int(input().strip()))

def ii():
	return int(input().strip())

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def solve(*args):
	(n, k, marks, participants) = args
	outp = list()
	for p in participants:
		outp.append(sum([x for (x, y) in zip(marks, p) if y == '1']))
	return outp

def do_codechef():
	for t in rii():
		(n, k) = mii()
		marks = lmii()
		participants = list()
		for _ in range(n):
			participants.append(si())
		print(*solve(n, k, marks, participants), sep='\n')
do_codechef()
exit()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	for i in range(n):
		r = str(input())
		l = list(map(int, r))
		s = 0
		for j in range(k):
			if l[j] == 1:
				s = s + p[j]
		print(s)