Monocarp has been collecting rare magazines for quite a while, and now he has decided to sell them. He distributed the magazines between $n$ boxes, arranged in a row. The $i$-th box contains $a_i$ magazines. Some of the boxes are covered with lids, others are not.

Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the $i$-th box was covered with a lid initially, he can either move the lid from the $i$-th box to the box $(i-1)$ (if it exists), or keep the lid on the $i$-th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak.

You have to calculate the maximum number of magazines Monocarp can save from the rain.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of the testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of boxes.

The second line contains a string of $n$ characters 0 and/or 1. If the $i$-th character is 1, the $i$-th box is initially covered with a lid. If the $i$-th character is 0, the $i$-th box is initially not covered.

The third line contains a sequence of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the number of magazines in the $i$-th box.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print one integer — the maximum number of magazines Monocarp can save from the rain.


-----Examples-----

Input
4
5
01110
10 5 8 9 6
6
011011
20 10 9 30 20 19
4
0000
100 100 100 100
4
0111
5 4 5 1
Output
27
80
0
14


-----Note-----

In the first testcase of the example, Monocarp can move the lid from the second box to the first box, so the boxes $1$, $3$ and $4$ are covered, and $10 + 8 + 9 = 27$ magazines are saved.

In the second testcase, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $1$, $2$, $4$ and $5$ will be covered, so $20 + 10 + 30 + 20 = 80$ magazines can be saved.

There are no lids in the third testcase, so it's impossible to save even a single magazine.

Difficulty: EASY
Tags: Greedy algorithms

Dynamic programming

Constructive algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1 << 30)

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	n = inp()
	s = insr()
	a = inlt()
	ans = 0
	idx = 0
	while idx < n:
		if s[idx] == '1':
			ans += a[idx]
			idx += 1
		else:
			c = a[idx]
			total = c
			idx += 1
			while idx < n and s[idx] == '1':
				c = min(c, a[idx])
				total += a[idx]
				idx += 1
			ans += total - c
	print(ans)
for _ in range(inp()):
	solve()


import sys
import sys, threading
from heapq import heapify, heappop, heappush
from math import log10, floor, pow, gcd, sqrt, inf
from collections import defaultdict, deque
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	tests = inp()
	for test in range(tests):
		numOfBoxes = inp()
		lid = insr()
		boxes = inlt()
		lid.append('0')
		boxes.append(0)
		currTotal = 0
		currMin = 0
		for i in range(numOfBoxes + 1):
			if lid[i] == '0':
				currTotal = currTotal - currMin + boxes[i]
				currMin = boxes[i]
			else:
				currTotal += boxes[i]
				currMin = min(currMin, boxes[i])
		print(currTotal)
main()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	lid = input().strip()
	arr = list(map(int, input().split()))
	dp = [0, 0]
	if lid[-1] == '1':
		dp = [0, arr[-1]]
	for i in range(n - 2, -1, -1):
		if lid[i] == '0':
			if lid[i + 1] == '1':
				dp = [max(dp[0] + arr[i], dp[1]), 0]
			else:
				dp = [max(dp), 0]
		elif lid[i + 1] == '1':
			dp = [max(arr[i] + dp[0], dp[1]), dp[1] + arr[i]]
		else:
			dp = [dp[0], dp[0] + arr[i]]
	return max(dp)
for _ in range(int(input())):
	print(solve())


def continuous(judge, magazines):
	o = judge.count('0')
	if o == 0:
		return sum(magazines)
	elif o == n:
		return 0
	sum_ = 0
	if judge.index('0') > judge.index('1'):
		sum_ += sum(magazines[:judge.index('0')])
	for i in range(n - 1):
		if judge[i] == '0' and judge[i + 1] == '1':
			l = i
			for j in range(i + 1, n):
				if judge[j] == '0':
					r = j - 1
					break
			else:
				r = n
			sum_ += sum(magazines[l:r + 1]) - min(magazines[l:r + 1])
	return sum_
import sys
input = sys.stdin.readline
t = int(input())
index = 0
for _ in range(t):
	n = int(input())
	judge = list(input())
	magazines = list(map(int, input().split()))
	print(continuous(judge, magazines))


def Pass(arr, ld):
	while True:
		for i in range(1, len(ld)):
			if ld[i - 1] == '0' and ld[i] == '1':
				temp_i = i
				min_i = i - 1
				MIN = arr[i - 1]
				while temp_i < len(ld) and ld[temp_i] == '1':
					if arr[temp_i] < MIN:
						MIN = arr[temp_i]
						min_i = temp_i
					temp_i += 1
				if min_i != i - 1:
					for k in range(i - 1, min_i):
						ld[k] = '1'
					ld[min_i] = '0'
		else:
			break
	SUM = 0
	for (l, x) in zip(ld, arr):
		if l == '1':
			SUM += x
	return SUM
OUTPUT = []
for _ in range(int(input())):
	N = int(input())
	ld = list(input())
	arr = [int(x) for x in input().split()]
	OUTPUT.append(Pass(arr, ld))
for _ in OUTPUT:
	print(_)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	a = list(map(int, input().split()))
	j = n
	count = 0
	for i in range(n):
		if s[i] != '1':
			j = i
			break
		count += a[i]
	if j != n:
		x = a[j]
	for i in range(j + 1, n):
		if s[i] == '1':
			if x > a[i]:
				count += x
				x = a[i]
			else:
				count += a[i]
		else:
			x = a[i]
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	open = input()
	numbers = list(map(int, input().split()))
	var = 0
	answer = 0
	index = 0
	for i in range(N):
		if open[i] == '0':
			var = numbers[i]
			index = i
		elif var > numbers[i]:
			answer += var
			var = numbers[i]
		else:
			answer += numbers[i]
	print(answer)


def magazine(n, string, mylist):
	result = 0
	tmp = 0
	for i in range(n):
		if string[i] == '1':
			result += max(mylist[i], tmp)
		if string[i] == '0' or mylist[i] < tmp:
			tmp = mylist[i]
	return result
numbers = int(input())
for i in range(numbers):
	n = int(input())
	string = input()
	mylist = list(map(int, input().split()))
	print(magazine(n, string, mylist))


def mainFunc():
	n = int(input())
	lidState = input()
	lidState = '0' + lidState
	boxContents = [0] + list(map(int, input().split()))
	ans = 0
	i = 0
	while i <= n:
		mn = boxContents[i]
		sm = boxContents[i]
		j = i + 1
		while j <= n and lidState[j] == '1':
			mn = min(mn, boxContents[j])
			sm += boxContents[j]
			j += 1
		ans += sm - mn
		i = j
	print(ans)
t = int(input())
for testcase in range(t):
	mainFunc()


def solve():
	n = int(input())
	s = '0' + input()
	arr = [0] + list(map(int, input().split()))
	x = 0
	ans = 0
	while x <= n:
		j = x + 1
		mn = arr[x]
		sm = arr[x]
		while j <= n and s[j] == '1':
			mn = min(arr[j], mn)
			sm += arr[j]
			j += 1
		sm -= mn
		ans += sm
		x = j
	print(ans)
t = int(input())
for i in range(t):
	solve()


def solve():
	n = int(input())
	s = list(input())
	arr = [int(i) for i in input().split()]
	j = -1
	for i in range(n):
		if s[i] == '0':
			j = i
		elif j >= 0 and arr[i] < arr[j]:
			(s[j], s[i]) = (s[i], s[j])
			j = i
	ans = 0
	for x in range(n):
		if s[x] == '1':
			ans += arr[x]
	print(ans)
tst = int(input())
for i in range(tst):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	a = list(map(int, input().split()))
	if s.count('1') == n:
		print(sum(a))
		continue
	ans = 0
	i = 0
	j = 1
	while i < n and s[i] == '1':
		i += 1
	ans += sum(a[:i])
	j = i + 1
	while j < n and i < n:
		if s[j] == '0':
			ans += max(0, sum(a[i:j]) - min(a[i:j]))
			i = j
		j += 1
	if i < n and s[-1] == '1':
		ans += max(0, sum(a[i:]) - min(a[i:]))
	print(ans)


def fun(l, arr, n):
	sum = 0
	i = n - 1
	while i > 0:
		if arr[i] == '1':
			a = i
			mini = l[a]
			d = a
			while i > 0 and arr[i] == '1':
				if l[i] < mini:
					mini = l[i]
					d = i
				i = i - 1
			if i == 0:
				if arr[i] == '1':
					break
			if mini < l[i]:
				arr[i] = '1'
				arr[d] = '0'
		i = i - 1
	for j in range(n):
		if arr[j] == '1':
			sum = sum + l[j]
	print(sum)
t = int(input())
for k in range(t):
	n = int(input())
	arr = []
	s = input()
	l = list(map(int, input().split()))
	for i in range(n):
		arr.append(s[i])
	fun(l, arr, n)


def solve1(n, arr, b):
	(res, l) = [0, -2147483647]
	for i in range(0, n):
		if arr[i] == '1':
			res += max(b[i], l)
		if arr[i] == '0' or b[i] < l:
			l = b[i]
	print(res)
for t in range(int(input())):
	n = int(input())
	s = [i for i in input()]
	a = [int(i) for i in input().split()]
	solve1(n, s, a)
	while None:
		pass
	while 1:
		break


def saveTheMagazines(tab, indexes, a1, j, n):
	j += 1
	sum = 0
	min = tab[j]
	for i in range(j, n):
		if indexes[i] == '0':
			return [i, max(sum + a1 - min, sum)]
		else:
			sum += tab[i]
			if min > tab[i]:
				min = tab[i]
	return [n, max(sum + a1 - min, sum)]
t = int(input())
result = []
for i in range(t):
	n = int(input())
	indexes = list(input())
	tab = list(map(int, input().split(' ')))
	sum = 0
	j = 0
	if (n == 1) & (indexes[0] == '1'):
		result.append(tab[0])
	else:
		while j < n - 1:
			if (indexes[j] == '0') & (indexes[j + 1] == '1'):
				res = saveTheMagazines(tab, indexes, tab[j], j, n)
				j = res[0]
				sum += res[1]
			elif indexes[j] == '1':
				sum += tab[j]
				j += 1
			else:
				j += 1
		if (j == n - 1) & (indexes[-1] == '1'):
			sum += tab[-1]
		result.append(sum)
for i in result:
	print(i)


t = int(input())
for t1 in range(t):
	n = int(input())
	lid = input()
	mag = list(map(int, input().split()))
	i = 0
	sum = 0
	while i < n and lid[i] == '1':
		sum += mag[i]
		i += 1
	while i < n and lid[i] == '0':
		while i + 1 < n and lid[i + 1] == '0':
			i += 1
		if i + 1 == n:
			break
		min = mag[i]
		csum = mag[i]
		i += 1
		while i < n and lid[i] == '1':
			if min > mag[i]:
				min = mag[i]
			csum += mag[i]
			i += 1
		sum += csum - min
	print(sum)


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a, s):
	s = list(map(int, list(s)))
	tot = 0
	i = 0
	l = 0
	(curS, curM) = (0, 1000000000.0)
	segs = []
	streak = False
	for i in range(n):
		if s[i] == 1:
			if not streak:
				l = i
			streak = True
		if s[i] == 0 and streak:
			segs.append([l, i - 1])
			streak = False
	if streak:
		segs.append([l, n - 1])
	for (x, y) in segs:
		if x == 0:
			for i in range(x, y + 1):
				tot += a[i]
		else:
			m = 1000000000.0
			for i in range(x - 1, y + 1):
				tot += a[i]
				m = min(m, a[i])
			tot -= m
	print(tot)
t = ni()
for case in range(t):
	n = ni()
	s = INP()
	a = nl()
	solve(n, a, s)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, b, n):
	pre = [0] * (n + 1)
	for i in range(n):
		pre[i + 1] = pre[i] + a[i]
	b += '0'
	a += [0]
	i = -1
	ans = 0
	for j in range(n + 1):
		if b[j] == '0':
			if i > -1:
				if i == 0:
					ans += pre[j]
				else:
					m = min(a[i - 1:j])
					ans += pre[j] - pre[i - 1] - m
			i = -1
			continue
		elif i == -1:
			i = j
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	b = input()
	a = list(map(int, input().split()))
	print(solve(a, b, n))


def solution():
	n = int(input())
	covers = '0' + input()
	a = [0] + [int(num) for num in input().split()]
	minimum = a[0]
	ones = False
	s = 0
	ans = 0
	for i in range(1, n + 1):
		if not ones:
			if covers[i] == '0':
				minimum = a[i]
				s = a[i]
			else:
				ones = True
				minimum = min(minimum, a[i])
				s += a[i]
		elif covers[i] == '0':
			ones = False
			ans += s - minimum
			minimum = a[i]
			s = a[i]
		else:
			minimum = min(minimum, a[i])
			s += a[i]
	if covers[-1] == '1':
		ans += s - minimum
	print(ans)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


from collections import Counter
import heapq

def solve():
	N = int(input())
	s = input()
	nums = [*map(int, input().split())]
	res = 0
	low = 0
	indx = [0] * N
	while low < N and s[low] == '1':
		res += nums[low]
		low += 1
	while low < N:
		h = []
		if low < N and s[low] == '0':
			low += 1
			continue
		else:
			heapq.heappush(h, -nums[low - 1])
			while low < N and s[low] == '1':
				heapq.heappush(h, -nums[low])
				res += abs(heapq.heappop(h))
				low += 1
	print(res)

def solution():
	t = int(input())
	for _ in range(t):
		solve()
solution()


def solve(A, s):
	v = []
	j = 0
	res = 0
	while j < len(A) and s[j] == '1':
		res += A[j]
		j += 1
	for i in range(j, len(A)):
		if s[i] == '0':
			if len(v):
				v.sort()
				res += sum(v[1:])
				v = []
			if i + 1 < len(A) and s[i + 1] == '1':
				v.append(A[i])
		elif s[i] == '1':
			v.append(A[i])
	if v:
		v.sort()
		res += sum(v[1:])
	return res

def main():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		A = list(map(int, input().split()))
		print(solve(A, s))
main()


from collections import deque
from math import inf

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		(*covered,) = map(int, list(input()))
		(*magazines,) = map(int, input().split())
		ans = 0
		i = 0
		while i <= n - 1:
			partial = 0
			mini = inf
			if covered[i]:
				ans += magazines[i]
				i += 1
			elif i < n - 1 and covered[i + 1]:
				partial += magazines[i]
				mini = magazines[i]
				j = i + 1
				while j < n and covered[j]:
					partial += magazines[j]
					mini = min(mini, magazines[j])
					j += 1
				ans += partial - mini
				i = j
			else:
				i += 1
		print(ans)
main()


I = input
for _ in [0] * int(I()):
	I()
	f = ('0' + I() + '0').find
	a = (0, *map(int, I().split()))
	i = j = r = 0
	while (i := f('01', j)) + 1:
		j = f('10', i)
		r += sum((b := a[i:j + 1])) - min(b)
	print(r)


for _ in range(int(input())):
	n = int(input())
	c = input()
	a = list(map(int, input().split()))
	(s, i) = (0, 0)
	while i < n:
		if c[i] == '1':
			s += a[i]
			i += 1
			continue
		if i == n - 1:
			break
		if c[i + 1] == '1':
			(m, t) = (a[i], a[i])
			j = i + 1
			while j < n and c[j] == '1':
				m = min(m, a[j])
				t += a[j]
				j += 1
			s += t - m
			i = j
		else:
			i += 1
	print(s)


def solve1(n1, arr, b):
	(res, l) = [0, -2147483647]
	for i in range(0, n1):
		if arr[i] == '1':
			res += max(b[i], l)
		if arr[i] == '0' or b[i] < l:
			l = b[i]
	print(res)
for i in range(int(input())):
	n1 = int(input())
	s = list(map(str, input()))
	l1 = list(map(int, input().split()))
	solve1(n1, s, l1)
	while None:
		pass
	while 1:
		break


def get_swap_snippet(roofs: list, start: int):
	left = 0
	right = 0
	try:
		first_roof = roofs.index('1', start)
	except ValueError:
		return -1
	if left != first_roof:
		left = first_roof - 1
	try:
		right = roofs.index('0', first_roof + 1)
	except ValueError:
		right = len(roofs)
	return (left, right)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		roofs = list(input())
		books = list(map(int, input().split()))
		general_sum = 0
		snippet = get_swap_snippet(roofs, 0)
		while snippet != -1:
			(left, right) = snippet
			general_sum += sum(books[left:right])
			if roofs[left] == '0':
				general_sum -= min(books[left:right])
			snippet = get_swap_snippet(roofs, right)
		print(general_sum)
main()


import bisect
import heapq
from collections import defaultdict, deque
from email import header
from functools import lru_cache
from sys import stdin, stdout
import math
import sys
input = stdin.readline

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

def lii():
	return list(map(int, stdin.readline().split()))

def ss():
	x = stdin.readline()
	if x[-1] == '\n':
		return x[:-1]
	return x

def lss():
	return list(map(str, stdin.readline().split()))

def llss():
	return [i for i in ss()]

def yes():
	stdout.write('YES\n')

def no():
	stdout.write('NO\n')
for _ in range(ii()):
	n = ii()
	s = ss()
	a = lii()
	res = 0
	i = 0
	while i < n:
		if s[i] == '1':
			curr = 0 if i == 0 else a[i - 1]
			j = i
			sm = 0 if i == 0 else a[i - 1]
			while j < n and s[j] == '1':
				sm += a[j]
				curr = min(curr, a[j])
				j += 1
			res += sm - curr
			i = j
		else:
			i += 1
	print(res)


p = int(input())
for i in range(0, p):
	n = int(input())
	lid = list(input())
	a = list(map(int, input().split()))
	s = 0
	j = 0
	fz = False
	while j < n:
		if lid[j] == '1':
			s = s + a[j]
			j = j + 1
		else:
			fz = True
			break
	if not fz:
		print(s)
	else:
		while j < n:
			while j < n and lid[j] == '0':
				j = j + 1
			s = a[j - 1] + s
			minn = a[j - 1]
			while j < n and lid[j] == '1':
				s = s + a[j]
				minn = min(minn, a[j])
				j = j + 1
			s = s - minn
		print(s)


for cases in range(int(input())):
	n = int(input())
	lid = list(input())
	box_ls = list(map(int, input().split()))
	max_num = 0
	if n == 0:
		print(0)
		continue
	j = 0
	while lid[j] != '0':
		max_num += box_ls[j]
		if j == n - 1:
			break
		j += 1
	p = n - 1
	while lid[p] != '1':
		if p == 0:
			break
		p -= 1
	k = p + 1
	for i in range(p, j - 1, -1):
		if lid[i] == '0':
			max_num += sum(box_ls[i:k]) - min(box_ls[i:k])
			k = i
	print(max_num)


def print_mag(length, lids, magazines):
	sum = 0
	last_zero = -1
	min = 1000000000
	for i in range(length + 1):
		if i == length or lids[i] == 0:
			if last_zero != -1 and last_zero != i - 1:
				if magazines[last_zero] > min:
					sum += magazines[last_zero]
					sum -= min
			last_zero = i
			min = 100000000
		elif lids[i] == 1:
			if min > magazines[i]:
				min = magazines[i]
			sum += magazines[i]
	print(sum)

def main():
	t = int(input())
	for i in range(t):
		length = int(input())
		lids = [int(num) for num in input()]
		magazines = [int(num) for num in input().split()]
		print_mag(length, lids, magazines)
main()


t = int(input())
for k in range(t):
	n = int(input())
	lids = input()
	l = list(map(int, input().split()))
	(i, check, min1) = (0, 0, 1000000)
	cnt = 0
	while i < n:
		while lids[i] == '1':
			cnt += l[i]
			min1 = min(min1, l[i])
			i += 1
			if i >= n:
				break
		if check == 1 and a > min1:
			cnt = cnt + a - min1
		min1 = 1000000
		if i < n:
			a = l[i]
			check = 1
			i += 1
	print(cnt)


def one():
	n = int(input())
	s = input()
	a = list(map(int, input().split()))
	p = [0]
	for e in a:
		p.append(p[-1] + e)
	c = 0
	i = 0
	while i < n:
		if s[i] == '0':
			i += 1
		else:
			j = i
			while i < n and s[i] == '1':
				i += 1
			if j > 0:
				c += p[i] - p[j - 1] - min(a[j - 1:i])
			else:
				c += p[i]
	print(c)
t = int(input())
for i in range(t):
	one()


t = int(input())
for t0 in range(t):
	c = int(input())
	s = input() + '0'
	a = list(map(int, input().split(' ')))
	a.append(0)
	pov = 0
	mn = 200001
	pvind = 0
	mnind = 0
	for i in range(c + 1):
		if s[i] == '0':
			if mn != 200001:
				if mn < pov:
					a[mnind] = pov
					a[pvind] = mn
				mn = 200001
			pov = a[i]
			pvind = i
		elif a[i] < mn:
			mn = a[i]
			mnind = i
	sum = 0
	for i in range(c):
		if s[i] == '1':
			sum += a[i]
	print(sum)


import math
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	a = list(map(int, input().split()))
	ct = 0
	i = n - 1
	while i >= 0:
		max = int(1000000000.0)
		if s[i] == '1':
			while i >= 0 and s[i] == '1':
				if a[i] < max:
					max = a[i]
				ct += a[i]
				i -= 1
			if i >= 0 and max < a[i]:
				ct += a[i] - max
		else:
			i -= 1
	print(ct)


for _ in range(int(input())):
	n = int(input())
	s = input()
	arr = list(map(int, input().split()))
	res = 0
	res2 = 0
	for i in range(n):
		if s[i] == '1':
			res += max(arr[i], res2)
		if s[i] == '0' or arr[i] < res2:
			res2 = arr[i]
	print(res)


for _ in range(int(input())):
	n = int(input())
	ld = list(input())
	a = list(map(int, input().split()))
	s = 0
	m = -1
	for i in range(1, n + 1):
		if ld[-i] == '1':
			s += a[-i]
			if a[-i] < m or m == -1:
				m = a[-i]
		else:
			if m > -1:
				s += a[-i]
				if a[-i] < m:
					m = a[-i]
				s -= m
			m = -1
	print(s)


import re
I = input
for _ in [0] * int(I()):
	I()
	s = '0' + I()
	a = (0, *map(int, I().split()))
	r = 0
	for m in re.finditer('01+', s):
		(s, e) = m.span()
		r += sum((b := a[s:e])) - min(b)
	print(r)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = list(map(int, input().split()))
	i = 0
	sm = 0
	while i < n:
		sm += a[i]
		if s[i] == '0':
			mn = a[i]
			i += 1
			while i < n and s[i] != '0':
				mn = min(mn, a[i])
				sm += a[i]
				i += 1
			sm -= mn
		else:
			i += 1
	print(sm)


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = list(map(int, input().split()))
	(maxi, li) = [0, -2147483647]
	for i in range(0, n):
		if s[i] == '1':
			maxi += max(l[i], li)
		if s[i] == '0' or l[i] < li:
			li = l[i]
	print(maxi)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = list(map(int, input().split()))
	(t, l) = [0, -2147483647]
	for i in range(0, n):
		if s[i] == '1':
			t += max(a[i], l)
		if s[i] == '0' or a[i] < l:
			l = a[i]
	print(t)


for _ in range(int(input())):
	n = int(input())
	string = '0' + input()
	arr = [0] + list(map(int, input().split()))
	ans = 0
	i = 0
	while i <= n:
		mn = arr[i]
		sm = arr[i]
		j = i + 1
		while j <= n and string[j] == '1':
			mn = min(mn, arr[j])
			sm += arr[j]
			j += 1
		ans += sm - mn
		i = j
	print(ans)


T = int(input())
for tc in range(T):
	k = int(input())
	s = input()
	l1 = list(map(int, input().split()))
	a = b = 0
	for i in range(0, k):
		if s[i] == '1':
			a += max(l1[i], b)
		if s[i] == '0' or l1[i] < b:
			b = l1[i]
	print(a)


for _ in range(int(input())):
	n = int(input())
	s = '0' + input()
	a = [0] + list(map(int, input().split()))
	ans = 0
	i = 0
	while i <= n:
		minimum = a[i]
		ans += a[i]
		j = i + 1
		while j <= n and s[j] == '1':
			minimum = min(minimum, a[j])
			ans += a[j]
			j += 1
		ans -= minimum
		i = j
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	b = input()
	a = [int(x) for x in input().split()]
	ans = 0
	for j in range(n):
		if b[j] == '1':
			ans += a[j]
		else:
			break
	if j == n - 1:
		print(ans)
	else:
		for i in range(j, n - 1):
			if b[i] == '0' and b[i + 1] == '1':
				don = a[i]
				ans += don
				small = don
			if b[i] == '1':
				ans += a[i]
				if a[i] < small:
					small = a[i]
			if b[i] == '1' and b[i + 1] == '0':
				ans -= small
		if b[-1] == '1':
			ans += a[-1]
			if small > a[-1]:
				small = a[-1]
			ans -= small
		print(ans)


I = input
for _ in [0] * int(I()):
	I()
	r = p = 0
	for (c, x) in zip(I(), map(int, I().split())):
		r += (c > '0') * max(p, x)
		p = (p, x)[c < '1' or x < p]
	print(r)


n = int(input())

def maxSave(n):
	for i in range(n):
		m = int(input())
		lids = list(str(input()))
		arr = list(map(int, input().split()))
		(total, i) = (0, 0)
		while i < m and lids[i] == '1':
			total += arr[i]
			i += 1
		while i < m:
			sum = arr[i]
			j = i + 1
			while j < m and lids[j] == '1':
				sum += arr[j]
				j += 1
			maxi = 0
			for k in range(i, j):
				maxi = max(maxi, sum - arr[k])
			total += maxi
			i = j
		print(total)
maxSave(n)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	mas = list(map(int, input().split()))
	ans = 0
	prom = 0
	for i in range(n):
		if s[i] == '1':
			ans += max(prom, mas[i])
		if s[i] == '0' or mas[i] < prom:
			prom = mas[i]
	print(ans)


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


t = int(input())
ans_l = []
for _ in range(t):
	n = int(input())
	boxs = [int(x) for x in input()]
	magas = [int(x) for x in input().split()]
	if n == 1:
		ans_l.append(boxs[0] * magas[0])
	else:
		ans = 0
		for i in range(n - 1):
			if boxs[i] == 0 and boxs[i + 1] == 1:
				j = i + 1
				mn = magas[i]
				c = i
				flag = False
				if magas[i + 1] < mn:
					flag = True
					c = i + 1
					mn = magas[i + 1]
				while j < n - 1:
					if boxs[j + 1] == 1:
						j += 1
					else:
						break
					if magas[j] < mn:
						mn = magas[j]
						flag = True
						c = j
				if flag:
					boxs[c] = 0
					ans += magas[i]
			elif boxs[i] == 1:
				ans += magas[i]
		if boxs[n - 1] == 1:
			ans += magas[n - 1]
		ans_l.append(ans)
for _ in range(t):
	print(ans_l[_])


for _ in range(int(input())):
	n = int(input())
	s = '0' + input()
	a = [0] + list(map(int, input().split()))
	answer = 0
	i = 0
	while i <= n:
		mn = a[i]
		sm = a[i]
		j = i + 1
		while j <= n and s[j] == '1':
			mn = min(mn, a[j])
			sm += a[j]
			j += 1
		answer += sm - mn
		i = j
	print(answer)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = list(map(int, input().split()))
	s = list(s)
	count = 0
	i = 0
	sum = 0
	min1 = 0
	while i < n:
		if s[i] == '0':
			count += sum - min1
			sum = a[i]
			min1 = a[i]
		else:
			sum += a[i]
			min1 = min(a[i], min1)
		i += 1
	if s[-1] == '1':
		count += sum - min1
	print(count)


k = int(input())
for m in range(k):
	n = int(input())
	s = input()
	a = list(map(int, input().split(' ')))
	minn = float('inf')
	ans = 0
	f = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			f = 1
			minn = min(minn, a[i])
			ans += a[i]
		elif f == 1:
			if a[i] > minn:
				ans += a[i] - minn
			f = 0
			minn = float('inf')
	print(ans)


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = list(map(int, input().split()))
	(X, p) = [0, -0]
	for i in range(0, a):
		if b[i] == '1':
			X += max(c[i], p)
		if b[i] == '0' or c[i] < p:
			p = c[i]
	print(X)


tst = int(input())
while tst > 0:
	no = int(input())
	ssr = input()
	mp = map(int, input().split())
	arr = list(mp)
	(f, p) = [0, -2147483647]
	for a in range(0, no):
		if ssr[a] == '1':
			f += max(arr[a], p)
		if ssr[a] == '0' or arr[a] < p:
			p = arr[a]
	print(f)
	tst = tst - 1


def main():
	t = int(input())

	def sol(lid, val, n):
		if n == 1 and lid[0] == '0':
			return 0
		elif n == 1:
			return val[0]
		s = 0
		i = 0
		while i < n - 1:
			if lid[i] == '0':
				j = i + 1
				mi = float('inf')
				while j < n and lid[j] == '1':
					s += val[j]
					mi = min(mi, val[j])
					j += 1
				if mi != float('inf') and mi < val[i]:
					s -= mi
					s += val[i]
				i = j
			else:
				s += val[i]
				i += 1
		if i == n - 1 and lid[i] == '1':
			s += val[i]
		return s
	for _ in range(t):
		n = int(input())
		lid = input()
		val = input().split()
		val = [int(val[i]) for i in range(n)]
		res = sol(lid, val, n)
		print(res)
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = list(map(int, input().split()))
	(res, ans) = (0, 0)
	for i in range(n):
		if s[i] == '1':
			res += max(a[i], ans)
		if s[i] == '0' or a[i] < ans:
			ans = a[i]
	print(res)


t = int(input())
for z in range(t):
	n = int(input())
	s = input()
	l = list(map(int, input().split()))
	c = []
	sum = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			c.append(l[i])
		elif s[i] == '0' and len(c) > 0:
			c.append(l[i])
			c.sort()
			for j in range(1, len(c)):
				sum += c[j]
			c = []
		if i == 0:
			for j in range(len(c)):
				sum += c[j]
	print(sum)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input()))
	a = list(map(int, input().split()))
	if s.count(s[0]) == n and s[0] == 0:
		print(0)
	elif s.count(s[0]) == len(s) and s[0] == 1:
		print(sum(a))
	else:
		count = 0
		b = 0
		for i in range(n):
			if s[i] == 1:
				if a[i] > b:
					count += a[i]
				else:
					count += b
			if a[i] < b or s[i] == 0:
				b = a[i]
		print(count)


for _ in range(int(input())):
	x = int(input())
	b = list(input())
	l = list(map(int, input().split()))
	c = 0
	las = -1
	for i in range(x):
		if b[i] == '1':
			c += max(las, l[i])
		if b[i] == '0' or l[i] < las:
			las = l[i]
	print(c)


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


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input())
	arr = list(map(int, input().split()))
	l_z = []
	l_o = []
	ans = 0
	i = 0
	while i < n:
		if s[i] == '1':
			ans += arr[i]
			i += 1
		else:
			curr = min_ = arr[i]
			j = i + 1
			while j < n and s[j] == '1':
				curr += arr[j]
				min_ = min(min_, arr[j])
				j += 1
			ans += curr - min_
			i = j
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	t = '0' + input()
	l = [0] + list(map(int, input().split(' ')))
	ans = 0
	i = 0
	while i <= n:
		minL = l[i]
		curL = l[i]
		j = i + 1
		while j <= n and t[j] == '1':
			minL = min(minL, l[j])
			ans += l[j]
			j += 1
		ans += curL - minL
		i = j
	print(ans)


import sys
for t in range(int(input())):
	n = int(input())
	a = '0' + input()
	s = [0] + list(map(int, input().split()))
	ans = 0
	i = 0
	while i < n:
		sm = s[i]
		mn = s[i]
		j = i + 1
		while j <= n and a[j] == '1':
			sm += s[j]
			mn = min(mn, s[j])
			j += 1
		ans += sm - mn
		i = j
	print(ans)


for _ in range(int(input())):
	n = int(input())
	wah = list(input())
	a = list(map(int, input().split(' ')))
	cnt = 0
	ccnt = 0
	start = 0
	minn = 0
	for i in range(0, n):
		if wah[i] == '0':
			cnt += ccnt - minn
			ccnt = a[i]
			minn = a[i]
		else:
			ccnt += a[i]
			minn = min(minn, a[i])
	if wah[-1] == '1':
		cnt += ccnt - minn
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	a = [x for x in str(input())]
	b = list(map(int, input().split()))
	ans = 0
	i = 0
	while i < n:
		if a[i] == '0' and i + 1 < n and (a[i + 1] == '1'):
			j = i + 1
			mn = b[i]
			su = b[i]
			while j < n and a[j] == '1':
				su += b[j]
				mn = min(b[j], mn)
				j += 1
			ans += su - mn
			i = j
		elif a[i] == '1':
			ans += b[i]
			i += 1
		else:
			i += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = list(map(int, input().split()))
	sum = 0
	last = -1
	for i in range(n):
		if a[i] == '1':
			sum += max(last, b[i])
		if a[i] == '0' or b[i] < last:
			last = b[i]
	print(sum)


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	mags = list(map(int, input().split()))
	ans = 0
	mx = -math.inf
	for i in range(len(s)):
		if s[i] == '1':
			ans += max(mx, mags[i])
		if s[i] == '0' or mx > mags[i]:
			mx = mags[i]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	binary_rep = list(input())
	boxes = list(map(int, input().split()))
	total = 0
	i = 1
	if binary_rep[0] == '1':
		total += boxes[0]
	while i < n:
		mn = 10000
		if binary_rep[i] == '1':
			if binary_rep[i - 1] == '0':
				mn = min(boxes[i - 1], mn)
				total += mn
				while i < n:
					if binary_rep[i] == '1':
						total += boxes[i]
						mn = min(mn, boxes[i])
						i += 1
					else:
						break
				total -= mn
			else:
				total += boxes[i]
				i += 1
		else:
			i += 1
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = list(map(int, input().split()))
	l = []
	i = 0
	count = 0
	while i < n:
		if i == 0 and s[i] == '1':
			if n != 1:
				if s[1] == '1':
					while i < n and s[i] == '1':
						count = count + a[i]
						i = i + 1
				else:
					count = count + a[0]
					i = i + 1
			else:
				count = count + a[0]
				i = i + 1
		elif i < n - 1:
			if s[i] == '0' and s[i + 1] == '1':
				l = []
				l.append(a[i])
				i = i + 1
				while i < n and s[i] == '1':
					l.append(a[i])
					i = i + 1
				b = min(l)
				l.remove(b)
				for j in l:
					count = count + j
			else:
				i = i + 1
		else:
			i = i + 1
	print(count)


t = int(input())
for k in range(t):
	n = int(input())
	arr1 = list(map(int, input()))
	arr2 = list(map(int, input().split()))
	ans = 0
	r = 0
	for i in range(n):
		if arr1[i] == 1:
			if arr2[i] > r:
				ans += arr2[i]
			else:
				ans += r
		if arr2[i] < r or arr1[i] == 0:
			r = arr2[i]
	print(ans)


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	st = [x for x in input()]
	arr = list(map(int, input().split()))
	(res1, res2) = (0, 0)
	for i in range(n):
		if st[i] == '1':
			res1 += max(arr[i], res2)
		if st[i] == '0' or arr[i] < res2:
			res2 = arr[i]
	print(res1)