Read problems statements in Mandarin Chinese  and Russian  

Chef is going to participate in a new quiz show: "Who dares to be a millionaire?"
According to the rules of the game, contestants must answer N questions. The quiz being famous for its difficulty, each question has 26 candidate answers, but only one of which is correct. Answers are denoted by capital Latin letters from A to Z. Chef knows all the questions that can be asked, and for each of them he knows the answer candidate he will choose (some of them can be incorrect). For each question, we'll tell you Chef's answer to it.
The game goes on as follows. First, all the questions are shuffled randomly. Then, a contestant is asked these questions one-by-one in the new shuffled order. If the contestant answers any question incorrectly, the game is over. Total winnings of the contestant are calculated as follows. Let X denote the number of questions answered correctly by the contestant. Depending on this value, the winnings are determined: W_{0} dollars is the amount won for X = 0, W_{1} dollars is for X = 1, and so on till X = N. Note that the game was invented by a twisted mind, and so a case where W_{i} ≥ W_{i + 1} for some 0 ≤ i ≤ N − 1 is possible.
Chef is interested in finding the maximum possible winnings that he can amass.

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

The first line of input contains an integer T denoting the number of test cases. The  description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of questions.
Next line contains N capital Latin letters denoting the correct answers to these questions.
Next line contains N capital Latin letters denoting answers given by Chef to these questions.
Next line contains N + 1 space-separated integers W_{0}, W_{1}, ..., W_{N} denoting the winnings for 0, 1, ..., N correct answers.

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

For each test case, output a single line containing the value of maximum possible winnings that Chef can get.

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

$1 ≤ T ≤ 500$
$1 ≤ N ≤ 1000$
$0 ≤ W_{i} ≤ 10^{9}$

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

Subtask 1: (20 points)
$1 ≤ N ≤ 8$
Subtask 2: (80 points)
$Original constraints$
----- Sample Input 1 ------ 
3
5
ABCDE
EBCDA
0 10 20 30 40 50
4
CHEF
QUIZ
4 3 2 1 0
8
ABBABAAB
ABABABAB
100 100 100 100 100 100 100 100 100
----- Sample Output 1 ------ 
30
4
100

------ Explanation 0 ------ 

Example case 1. If questions will be placed in order: 2^{nd} (Chef's answer is B, which is correct), 3^{rd} (Chef's answer is C, and it is correct as well), 4^{th} (Chef's answer is D, and he is right), 5^{th} (Chef's answer is A but correct answer is E and the game is over), 1^{st}, Chef will correctly answer 3 questions, and therefore win 30 dollars.
Example case 2. Chef's answers for all questions are incorrect, so his winnings are W0 dollars.
Example case 3. Since all Wi are equal to 100 dollars, Chef will win this sum in any possible case.

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	ques = input()
	ans = input()
	l = [int(x) for x in input().split()]
	s = 0
	for i in range(n):
		if ques[i] == ans[i]:
			s = s + 1
	if s < n:
		print(max(l[0:s + 1]))
	else:
		print(l[-1])


for _ in range(int(input())):
	n = int(input())
	crt_ans = [i for i in input()]
	chf_ans = [j for j in input()]
	w = list(map(int, input().split(' ')))
	cnt = 0
	for k in range(0, n):
		if crt_ans[k] == chf_ans[k]:
			cnt += 1
	if cnt == n:
		print(w[-1])
	else:
		print(max(w[:cnt + 1]))


T = int(input())
for i in range(0, T):
	n = int(input())
	corAns = input()
	cefAns = input()
	summ = 0
	cora = 0
	b = input().split()
	for j in range(0, n + 1):
		b[j] = int(b[j])
	corAns = list(corAns)
	cefAns = list(cefAns)
	for j in range(0, n):
		if corAns[j] == cefAns[j]:
			cora += 1
	if cora == 0:
		print(b[0])
	elif cora == n:
		print(b[n])
	else:
		summ = b[0]
		for j in range(1, cora + 1):
			summ = max(summ, b[j])
		print(summ)


T = int(input())
for i in range(T):
	N = int(input())
	chef = input()
	corr = input()
	w = list(map(int, input().split()))
	count = 0
	for (x, y) in zip(chef, corr):
		if x == y:
			count += 1
	if count == N:
		print(w[N])
	else:
		print(max(w[:count + 1]))


T = int(input())
for i in range(0, T):
	N = int(input())
	answers = input()
	canswers = input()
	temp = input().split()
	correct = 0
	biggest = -1
	winnings = [int(a) for a in temp]
	for i in range(0, len(answers)):
		if canswers[i] == answers[i]:
			correct = correct + 1
	for g in range(0, correct + 1):
		if winnings[g] > biggest:
			biggest = winnings[g]
	if correct == len(answers):
		print(winnings[len(winnings) - 1])
	else:
		print(biggest)


for _ in range(int(input())):
	x = int(input())
	ans = input()
	chef = input()
	reward = list(map(int, input().split()))
	same = 0
	for i in range(x):
		if ans[i] == chef[i]:
			same += 1
	if same == x:
		print(reward[-1])
	else:
		print(max(reward[0:same + 1]))


a = int(input())
for i in range(a):
	b = int(input())
	c = input()
	d = input()
	e = list(map(int, input().split()))
	count = 0
	for i in range(b):
		if c[i] == d[i]:
			count += 1
	if count == 0:
		print(e[0])
	elif count == b:
		print(e[b])
	else:
		print(max(e[:count + 1]))


for i in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	c = list(map(int, input().split()))
	t = 0
	if a == b:
		print(c[-1])
	else:
		for j in range(n):
			if a[j] == b[j]:
				t = t + 1
		print(max(c[:t + 1]))


for _ in range(int(input())):
	n = int(input())
	s1 = list(input().upper())
	s2 = list(input().upper())
	w = [int(x) for x in input().split()]
	c = 0
	uc = 0
	for i in range(n):
		if s1[i] == s2[i]:
			c += 1
	if c == 0 or len(set(w)) == 1:
		print(w[0])
		continue
	elif c == n:
		print(w[n])
		continue
	else:
		print(max(w[:c + 1]))


def solve(a, b, w, n):
	ans = 0
	for i in range(n):
		if a[i] == b[i]:
			ans += 1
	if ans == n:
		return w[n]
	return max(w[0:ans + 1])
for _ in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	w = [int(j) for j in input().split()]
	print(solve(a, b, w, n))


t = int(input())
for _ in range(t):
	n = int(input())
	r = input()
	c = input()
	w = list(map(int, input().split()))
	nb = 0
	for i in range(len(r)):
		if r[i] == c[i]:
			nb += 1
	if nb < n:
		print(max(w[:nb + 1]))
	else:
		print(w[-1])


for _ in range(int(input())):
	n = int(input())
	q = input()
	a = input()
	arr = list(map(int, input().split()))
	wrong_a = 0
	for i in range(n):
		if q[i] != a[i]:
			wrong_a += 1
	if wrong_a == 0:
		print(arr[n])
	else:
		print(max(arr[:len(arr) - wrong_a]))


t = int(input())
for _ in range(t):
	n = int(input())
	q = input()
	a = input()
	list1 = list(map(int, input().split()))
	temp = list1[0]
	count = 0
	j = 0
	for i in range(n):
		if q[i] == a[i]:
			j = j + 1
			if list1[j] > temp:
				temp = list1[j]
			count = count + 1
	if count == n:
		print(list1[n])
	else:
		print(temp)


for _ in range(int(input())):
	n = int(input())
	corr = input()
	give = input()
	w = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if corr[i] == give[i]:
			count += 1
	if count == n:
		print(w[n])
	else:
		print(max(w[:count + 1]))


t = int(input())
for _ in range(t):
	n = int(input())
	cans = input()
	ans = input()
	values = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if cans[i] == ans[i]:
			count += 1
	if count == n:
		print(values[n])
	else:
		print(max(values[:count + 1]))


for t in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	m = list(map(int, input().split()))
	count = 0
	for x in range(n):
		if s1[x] == s2[x]:
			count += 1
	mx = 0
	if count == 0:
		print(m[0])
	elif count == n:
		print(m[n])
	else:
		for i in range(count + 1):
			mx = max(mx, m[i])
		print(mx)


for _ in range(int(input())):
	n = int(input())
	correct = input()
	chef = input()
	w = list(map(int, input().split(' ')))
	win = 0
	for i in range(len(correct)):
		if correct[i].upper() == chef[i].upper():
			win = win + 1
	if win < n:
		print(max(w[:win + 1]))
	else:
		print(w[win])


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	p = input()
	lst = [int(x) for x in input().split()]
	count = 0
	for i in range(n):
		if s[i] == p[i]:
			count += 1
	if count == n:
		print(lst[n])
	else:
		print(max(lst[0:count + 1]))


for tc in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	w = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if a[i] == b[i]:
			c += 1
	if c == n:
		print(w[n])
	else:
		print(max(w[:c + 1]))


for T in range(int(input())):
	N = int(input())
	Ans = tuple(input())
	Given_ans = tuple(input())
	price = tuple(map(int, input().split(' ')))
	streak = 0
	for (index, letter) in enumerate(Ans):
		streak += 1 if Given_ans[index] == letter else 0
	if streak < N:
		print(max((price[x] for x in range(streak + 1))))
	else:
		print(price[streak])


T = int(input())
for i in range(T):
	N = int(input())
	ans = list(input())
	giv = list(input())
	price = list(map(int, input().split()))
	cor = 0
	for (i, j) in zip(ans, giv):
		if i == j:
			cor += 1
	if cor == N:
		print(price[-1])
	else:
		s = max(price[:cor + 1])
		print(s)


for i in range(int(input())):
	n = int(input())
	cr = input()
	ch = input()
	c = 0
	ans = 0
	ma = list(map(int, input().split()))
	for j in range(n):
		if ch[j] == cr[j]:
			c = c + 1
	m = ma.index(max(ma))
	if c == 0:
		print(ma[0])
	elif c == n:
		print(ma[c])
	elif c >= m:
		print(ma[m])
	else:
		while c < m:
			ma[m] = -1
			m = ma.index(max(ma))
		print(ma[m])


for _ in range(int(input())):
	n = int(input())
	a = input()
	c = input()
	w = list(map(lambda x: int(x), input().split()))
	co = 0
	for i in range(0, n):
		if a[i] == c[i]:
			co += 1
	if co == n:
		print(w[n])
	else:
		print(max(w[:co + 1]))


for i in range(int(input())):
	n = int(input())
	correctans = input()
	givenans = input()
	prize = list(map(int, input().split()))
	flag = 0
	for i in range(n):
		if correctans[i] == givenans[i]:
			flag += 1
		else:
			pass
	if flag == n:
		print(prize[n])
	else:
		print(max(prize[0:flag + 1]))


for _ in range(int(input())):
	n = int(input())
	correct_answers = input()
	responses = input()
	winnings = list(map(int, input().split()))
	num_correct = 0
	for i in range(n):
		if correct_answers[i] == responses[i]:
			num_correct += 1
	if num_correct == n:
		print(winnings[-1])
	else:
		print(max(winnings[:num_correct + 1]))


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	w = list(map(int, input().split()))
	count = 0
	for (x, y) in zip(s1, s2):
		if x == y:
			count += 1
	if count == n:
		print(w[n])
	else:
		print(max(w[:count + 1]))


for i in range(int(input())):
	n = int(input())
	a = input()
	c = input()
	count = 0
	w = [int(i) for i in input().split()]
	for i in range(n):
		if a[i] == c[i]:
			count += 1
	if count == n:
		print(w[n])
	else:
		m = 0
		for j in range(count + 1):
			if m < w[j]:
				m = w[j]
		print(m)


import sys
T = int(sys.stdin.readline())
for t in range(T):
	N = int(sys.stdin.readline().strip())
	A = list(sys.stdin.readline().strip())
	C = list(sys.stdin.readline().strip())
	W = list(map(int, sys.stdin.readline().strip().split()))
	nbsol = 0
	for i in range(N):
		if A[i] == C[i]:
			nbsol += 1
	if nbsol == N:
		sys.stdout.write(str(W[N]) + '\n')
	else:
		sys.stdout.write(str(max(W[:nbsol + 1])) + '\n')


cases = int(input())
for case in range(cases):
	questions = int(input())
	answer_key = input()
	chef_answers = input()
	winnings = list(map(int, input().split()))
	correct_answers = 0
	for i in range(questions):
		if answer_key[i] == chef_answers[i]:
			correct_answers += 1
	if correct_answers == questions:
		print(winnings[correct_answers])
	else:
		print(max(winnings[:-(questions - correct_answers)]))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	x = 0
	arr = [int(l) for l in input().split()]
	for i in range(n):
		if a[i] == b[i]:
			x += 1
	if x == n:
		print(arr[x])
	else:
		print(max(arr[:x + 1]))


for _ in range(int(input())):
	(n, correct) = (int(input()), 0)
	if 1 <= n <= 1000:
		corr_ans = list(input())
		chef_ans = list(input())
		money = list(map(int, input().split()))
		for i in range(n):
			if corr_ans[i] == chef_ans[i]:
				correct += 1
		if correct == n:
			print(money[correct])
		else:
			max = 0
			for i in range(0, correct + 1):
				if max < money[i]:
					max = money[i]
			print(max)


for _ in range(int(input())):
	n = int(input())
	cor = input()
	ans = input()
	w = [int(i) for i in input().split()]
	count = 0
	for i in range(n):
		if cor[i] == ans[i]:
			count += 1
	if count == n:
		print(w[n])
	else:
		print(max(w[:count + 1]))


try:
	for _ in range(int(input())):
		N = int(input())
		L1 = input()
		L2 = input()
		S = list(map(int, input().split()))
		if L1 == L2:
			print(S[-1])
		else:
			c = 0
			for i in range(N):
				if L1[i] == L2[i]:
					c += 1
			print(max(S[:c + 1]))
except:
	pass


def streak(valid: str, given: str):
	valid = [x for x in valid]
	given = [x for x in given]
	counter = 0
	for (v, g) in zip(valid, given):
		if v == g:
			counter += 1
	return counter
t = int(input())
for i in range(t):
	n = int(input())
	correct = input()
	chef = input()
	winnings = list(map(int, input().split(' ')))
	maxStreak = streak(correct, chef)
	if n == maxStreak:
		print(winnings[n])
	else:
		print(max(winnings[0:maxStreak + 1])) if maxStreak > 0 else print(winnings[0])


t = int(input())
for i in range(t):
	n = int(input())
	ca = str(input())
	cha = str(input())
	w = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if ca[i] == cha[i]:
			c = c + 1
	if c == n:
		print(w[n])
	else:
		print(max(w[:c + 1]))


for _ in range(int(input())):
	n = int(input())
	correct_ans = input()
	chef_ans = input()
	w = list(map(int, input().split()))
	count = 0
	maxval = 0
	for (i, j) in zip(correct_ans, chef_ans):
		if i == j:
			count += 1
	print(w[-1]) if count == n else print(max(w[:count + 1]))


T = int(input())
for _ in range(T):
	n = int(input())
	correctAnswers = input()
	badAnswers = input()
	points = [int(i) for i in input().split(' ')]
	ok = 0
	for i in range(n):
		if correctAnswers[i] == badAnswers[i]:
			ok += 1
	if ok == len(correctAnswers):
		print(points[ok])
		continue
	if ok == 0:
		print(points[0])
		continue
	maxPoint = points[0]
	for i in range(1, ok + 1):
		maxPoint = max(maxPoint, points[i])
	print(maxPoint)


t = int(input())
for j in range(t):
	n = int(input())
	a = input()
	c = input()
	co = 0
	w = list(map(int, input().split(' ')))
	for k in range(n):
		if a[k] == c[k]:
			co = co + 1
	if co == n:
		print(w[n])
	else:
		print(max(w[:co + 1]))


for _ in range(int(input())):
	n = int(input())
	correct = list(str(input()))
	chef = list(str(input()))
	price = list(map(int, input().split()))
	c = 0
	a = 0
	for i in range(n):
		if correct[i] == chef[i]:
			c += 1
	if c == n:
		print(price[c])
	else:
		print(max(price[0:c + 1]))


for _ in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = input()
	arr = list(map(int, input().split()))
	cnt = 0
	for (x, y) in zip(s1, s2):
		if x == y:
			cnt += 1
	if cnt == n:
		print(arr[cnt])
	else:
		print(max(arr[:cnt + 1]))


t = int(input())
for x in range(t):
	n = int(input())
	a = input()
	b = input()
	w = [int(d) for d in input().split()]
	count = 0
	for i in range(len(a)):
		if a[i] == b[i]:
			count += 1
	if a == b:
		print(w[len(a)])
	else:
		print(max(w[0:count + 1]))


for t in range(int(input())):
	n = int(input())
	correct = [i for i in input()]
	chef = [i for i in input()]
	w = [int(i) for i in input().split()]
	corr = 0
	for i in range(n):
		if correct[i] == chef[i]:
			corr += 1
	if corr == n:
		print(w[n])
	else:
		max = w[0]
		for i in range(corr + 1):
			if w[i] > max:
				max = w[i]
		print(max)


def main():
	t = int(input())
	for case in range(t):
		n = int(input())
		key = input()
		answers = input()
		score = sum([1 for i in range(n) if answers[i] == key[i]])
		points = [int(i) for i in input().split()]
		if score == n:
			print(points[-1])
			continue
		max_score = points[0]
		for i in range(1, score + 1):
			max_score = max(max_score, points[i])
		print(max_score)
main()


t = int(input())
for i in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	l = list(map(int, input().split()))
	count = 0
	for i in range(len(s1)):
		if s1[i] == s2[i]:
			count += 1
	if count == n:
		print(l[n])
	else:
		print(max(l[:count + 1]))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	q = input()
	a = input()
	arr = list(map(int, input().split()))
	wrong_a = 0
	for i in range(n):
		if q[i] != a[i]:
			wrong_a += 1
	if wrong_a == 0:
		print(arr[n])
	elif wrong_a == n:
		print(arr[0])
	else:
		print(max(arr[0:len(arr) - wrong_a]))


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = input()
	c = [int(i) for i in input().split()]
	d = 0
	for i in range(n):
		if a[i] == b[i]:
			d += 1
	if d == n:
		print(c[n])
	else:
		print(max(c[:d + 1]))


T = int(input())
for i in range(T):
	N = int(input())
	corr = input()
	ques = input()
	W = list(map(int, input().split()))
	corr_l = list(corr)
	ques_l = list(ques)
	ans = 0
	for j in range(len(corr_l)):
		if corr_l[j] == ques_l[j]:
			ans += 1
	if corr_l == ques_l:
		print(W[len(corr_l)])
	elif W[ans] == max(W[0:ans + 1]):
		print(W[ans])
	else:
		print(max(W[0:ans + 1]))


for t in range(int(input())):
	n = int(input())
	a = input()
	g = input()
	w = list(map(int, input().split()))
	r = 0
	for i in range(n):
		c = a[i]
		d = g[i]
		if a[i] == g[i]:
			r += 1
	if r == n:
		print(w[n])
	else:
		w = w[:r + 1]
		print(max(w))


for _ in range(int(input())):
	n = int(input())
	c = input()
	a = input()
	w = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if a[i] == c[i]:
			count += 1
	if count == n:
		print(w[-1])
	else:
		print(max(w[:count + 1]))


t = int(input())
for _ in range(t):
	n = int(input())
	c = input()
	ch = input()
	w = list(map(int, input().split()))
	z = 0
	for i in range(n):
		if c[i] == ch[i]:
			z += 1
	if z == n:
		print(w[n])
	else:
		print(max(w[0:z + 1]))


for _ in range(int(input())):
	N = int(input())
	A = list(input())
	C = list(input())
	W = list(map(int, input().split()))
	c = 0
	for (i, j) in zip(A, C):
		if i == j:
			c += 1
	if c < N:
		print(max(W[:c + 1]))
	else:
		print(W[-1])


t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	correctAns = input()
	chefAns = input()
	points = list(map(int, input().split(' ')))
	for j in range(n):
		if correctAns[j] == chefAns[j]:
			count += 1
	if count < n:
		print(max(points[0:count + 1]))
	else:
		print(points[-1])


t = int(input())
for _ in range(t):
	n = int(input())
	s1 = input()
	s2 = input()
	li = list(map(int, input().split()))
	d = 0
	for i in range(n):
		if s1[i] == s2[i]:
			d += 1
	if d == n:
		print(li[n])
	else:
		print(max(li[:d + 1]))


tests = int(input())
for i in range(tests):
	ques = int(input())
	ans_string = input()
	chef_ans = input()
	prizes = list(map(int, input().split()))
	ans = 0
	for j in range(ques):
		if ans_string[j] == chef_ans[j]:
			ans += 1
	if ans < ques:
		print(max(prizes[:ans + 1]))
	else:
		print(prizes[ans])


test = int(input())
for i in range(test):
	questions = int(input())
	answers = input()
	input_str = input()
	List = list(map(int, input().split()))
	winings = 0
	winings_price = [List[0]]
	for i in range(questions):
		if answers[i] == input_str[i]:
			winings = winings + 1
	if winings == questions:
		print(int(List[winings]))
	else:
		List = List[:winings + 1]
		List.sort(reverse=True)
		print(List[0])


T = int(input())
for w in range(T):
	N = int(input())
	correct = input()
	chef = input()
	prize = list(map(int, input().split()))
	count = 0
	for i in range(N):
		if correct[i] == chef[i]:
			count += 1
	if count == N:
		print(prize[-1])
	else:
		print(max(prize[:count + 1]))


for t in range(int(input())):
	n = int(input())
	x = input()
	y = input()
	w = [int(i) for i in input().split(' ')]
	ca = 0
	for i in range(n):
		if x[i] == y[i]:
			ca += 1
	if ca < n:
		print(max(w[0:ca + 1]))
	else:
		print(w[-1])


for i in range(int(input())):
	n = int(input())
	ans = input()
	chef = input()
	l = [int(x) for x in input().split()]
	c = 0
	for i in range(n):
		if ans[i] == chef[i]:
			c += 1
	if c == n:
		print(l[c])
	else:
		print(max(l[0:c + 1]))


for _ in range(int(input())):
	n = int(input())
	c = 0
	C = input()
	A = input()
	for i in range(n):
		c += 1 if C[i] == A[i] else 0
	W = list(map(int, input().split()))
	if c < n:
		print(max(W[:c + 1]))
	else:
		print(W[c])


for tc in range(int(input())):
	n = int(input())
	correct = input()
	answers = input()
	reward = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if correct[i] == answers[i]:
			count += 1
	if count == n:
		print(reward[n])
	else:
		print(max(reward[:count + 1]))


for x in range(int(input())):
	n = int(input())
	a = input()
	b = input()
	data = [int(d) for d in input().split()]
	final = 0
	if a == b:
		print(data[-1])
	else:
		for j in range(n):
			if a[j] == b[j]:
				final = final + 1
		print(max(data[:final + 1]))