There are n villages in a Chefland. Some of the villages have electricity facilities, other doesn't. You can consider the villages arranged in line in the order 1 to n from left to right. i-th of village can be considered at xi coordinates.

Chef decided that electricity should be provided to all the villages. So, he decides to buy some amount of electric wires to connect the villeges without electricity to some villages with electricity. As Chef does not want to spend too much amount of money on wires, can you find out minimum amount of length of wire Chef should buy.

-----Input-----
First line of the input contains an integer T denoting the number of test cases. T test cases follow.
First line of each test case contains an integer n denoting number of villages in Chefland.
Second line will contain a string of length n containing '0' or '1's only. If i-th character of the string is '1', then it denotes that i-th village has electricity.
Next line contains n space separated integers denoting the x coordinates of the villages in the order from village 1 to n

-----Output-----
For each test case, output a single line containing a integer corresponding to the minimum length of wire Chef needs to buy.

-----Constraints-----
- 1 ≤ T ≤ 10
- It is guaranteed that there will be at least one village which will have electricity.
- 1 ≤ x1 <  x2 <  ... < xn ≤ 109

-----Subtasks-----
Subtask #1 : 30 points
- 1 ≤ N ≤ 1000

Subtask #2 : 70 points
- 1 ≤ N ≤ 105

-----Example-----
Input
2
2
01
1 2
3
100
1 5 6
Output:
1
5

-----Explanation-----
In the first example, first village does not have electricity. If we put a wire between village 1 and 2 of length 1, then both the villages will have electricity.

In the second example,
We can a draw a wire from first village to third village, passing through second village. Its total length will be 5. Now all the villages will have electricity. This is the minimum length of wire you will require.

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

Starter code:

Solutions:
t = int(input())
for z in range(t):
	n = int(input().strip())
	s = input().strip()
	x = [int(i) for i in input().strip().split()]
	lit = [int(s[i]) for i in range(n)]
	(lm, rm) = (-1, -1)
	for i in range(n):
		if s[i] == '1':
			lm = i
			break
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			rm = i
			break
	ans = 0
	d = {}
	ans += x[lm] + x[-1] - x[rm] - x[0]
	tmp = x[rm] - x[lm]
	ma = 0
	for i in range(lm + 1, rm + 1):
		if s[i] == '1':
			if x[i] - x[i - 1] > ma:
				ma = x[i] - x[i - 1]
			tmp -= ma
			ma = 0
		elif x[i] - x[i - 1] > ma:
			ma = x[i] - x[i - 1]
	ans += tmp
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = list(input())
	coord = list(map(int, input().split()))
	p = 0
	i = 0
	h = []
	for i in range(0, n):
		if s[i] == '1':
			h.append(i)
	if h[0] != 0:
		p = p + coord[h[0]] - coord[0]
	if h[len(h) - 1] != n - 1:
		p = p + coord[n - 1] - coord[h[len(h) - 1]]
	for j in range(0, len(h) - 1):
		if h[j] + 1 == h[j + 1]:
			continue
		if h[j + 1] - h[j] - 1 == 1:
			p = p + min(coord[h[j] + 1] - coord[h[j]], coord[h[j + 1]] - coord[h[j] + 1])
		else:
			y = min(coord[h[j + 1]] - coord[h[j] + 1], coord[h[j + 1] - 1] - coord[h[j]])
			for k in range(h[j] + 1, h[j + 1] - 1):
				y = min(y, coord[k] - coord[h[j]] + coord[h[j + 1]] - coord[k + 1])
			p = p + y
	print(p)


tests = int(input())
for _ in range(tests):
	n = int(input())
	s = input()
	d = list(map(int, input().split()))
	mdiff = -1
	(r, l, ans) = (int(), 0, 0)
	if s[0] == '0':
		while s[l] == '0':
			l += 1
		ans += d[l] - d[0]
	r = n - 1
	if s[n - 1] == '0':
		r = n - 1
		while s[r] != '1':
			r -= 1
		ans += d[n - 1] - d[r]
	i = l + 1
	while i <= r:
		if d[i] - d[i - 1] > mdiff:
			mdiff = d[i] - d[i - 1]
		if s[i] == '1':
			if s[i - 1] == '0':
				lt = d[i] - d[l]
				ans += lt - mdiff
			l = i
			mdiff = -1
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = list(map(int, input().split()))
	p = []
	cum = 0
	l = 0
	for j in range(n):
		if s[j] == '1':
			p += [j]
			l += 1
	j = 0
	k = 0
	if p[k] == j:
		k += 1
	else:
		while j < p[k]:
			z = x[j + 1] - x[j]
			cum += z
			j += 1
		k += 1
	while j < n:
		if k == l:
			while j < n - 1:
				z = x[j + 1] - x[j]
				cum += z
				j += 1
			break
		m = 0
		while j < p[k]:
			z = x[j + 1] - x[j]
			cum += z
			if m < z:
				m = z
			j += 1
		cum -= m
		k += 1
	print(cum)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	s = input()
	l = list(map(int, input().split()))
	c = 0
	t1 = 0
	t2 = 0
	while c < n:
		if s[c] == '1':
			j = c + 1
			m = -float('inf')
			while j < n and s[j] == '0':
				t2 += l[j] - l[j - 1]
				if l[j] - l[j - 1] > m:
					m = l[j] - l[j - 1]
				j += 1
			if j < n and s[j] == '1':
				t2 += l[j] - l[j - 1]
				if l[j] - l[j - 1] > m:
					m = l[j] - l[j - 1]
				t2 -= m
				t1 += t2
				t2 = 0
			c = j
		else:
			c += 1
	x = 0
	for z in range(n - 1):
		if s[z] == '1':
			break
		x += l[z + 1] - l[z]
	t1 += t2 + x
	ans.append(t1)
for u in ans:
	print(u)


for _ in range(int(input())):
	n = int(input())
	s = input()
	arr = [int(i) for i in input().split()]
	ans = 0
	i = 0
	if s[0] == '0':
		while i < len(s) - 1 and s[i] != '1':
			ans += arr[i + 1] - arr[i]
			i += 1
	if i == len(s) - 1:
		print(ans)
		continue
	j = n - 1
	if s[n - 1] == '0':
		while j > 0 and s[j] != '1':
			ans += arr[j] - arr[j - 1]
			j -= 1
	if j == 0:
		print(ans)
		continue
	k = i
	while k < j:
		if s[k + 1] == '1':
			k += 1
			continue
		maxi = -1
		while s[k + 1] != '1':
			ans += arr[k + 1] - arr[k]
			maxi = max(maxi, arr[k + 1] - arr[k])
			k += 1
		ans += arr[k + 1] - arr[k]
		maxi = max(maxi, arr[k + 1] - arr[k])
		if maxi != -1:
			ans -= maxi
		k += 1
	print(ans)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	N = int(sys.stdin.readline())
	B = [True] + [bool(int(x)) for x in sys.stdin.readline().strip()] + [True]
	X = [-10 ** 18] + [int(x) for x in sys.stdin.readline().split()] + [10 ** 18]
	s = 0
	mx = -1
	o = 0
	for i in range(1, N + 2):
		if mx < X[i] - X[i - 1]:
			mx = X[i] - X[i - 1]
		if B[i]:
			if not B[i - 1]:
				s += X[i] - X[o] - mx
			mx = -1
			o = i
	print(s)


T = int(input())
for t in range(T):
	N = int(input()) + 2
	s = '1' + input() + '1'
	A = [-10000000000] + [int(x) for x in input().split()] + [10000000000]
	ss = 0
	mm = 0
	ans = 0
	for i in range(1, N):
		ss += A[i] - A[i - 1]
		mm = max(mm, A[i] - A[i - 1])
		if s[i] == '1':
			ans += ss - mm
			ss = 0
			mm = 0
	print(ans)


T = int(input())
for tt in range(T):
	(x, N) = (0, int(input()))
	S = input() + '$'
	A = [int(y) for y in input().split(' ')]
	cost = 0
	while x < N:
		if S[x] == '0':
			(start, end) = (x, x)
			while S[end] == '0':
				end += 1
			if start == 0:
				cost += A[end] - A[0]
			elif end == N:
				cost += A[N - 1] - A[start - 1]
			else:
				t_cost = 1000000000
				for i in range(start, end + 1):
					t_cost = min(t_cost, A[end] - A[i] + A[i - 1] - A[start - 1])
				cost += t_cost
			x = end
		else:
			x += 1
	print(cost)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = [int(temp) for temp in input().strip().split(' ')]
	f = 0
	l = 0
	sm = 0
	for b in range(len(s)):
		if s[b] == '1':
			f = l = b
			sm += a[f] - a[0]
			break
	for i in range(f + 1, len(s)):
		if s[i] == '1':
			l = i
			max = 0
			for k in range(f, l):
				curr = a[k + 1] - a[k]
				if curr > max:
					max = curr
			sm += a[l] - a[f] - max
			f = l
	sm += a[n - 1] - a[l]
	print(sm)


for t in range(int(input())):
	N = int(input())
	s = input()
	elec = list(map(int, list(s)))
	villages = list(map(int, input().split()))
	power = [i for (i, v) in enumerate(elec) if v == 1]
	ans = 0
	if len(power) == 1:
		idx = elec.index(1)
		if idx == 0 or idx == N - 1:
			ans = villages[-1] - villages[0]
		else:
			ans = villages[idx] - villages[0] + villages[-1] - villages[idx]
	else:
		if elec[0] == 0:
			ans += villages[elec.index(1)] - villages[0]
		if elec[-1] == 0:
			ans += villages[-1] - villages[s.rfind('1')]
		for i in range(len(power) - 1):
			min_sum = 1 << 30
			for s in range(power[i], power[i + 1]):
				min_sum = min(min_sum, villages[s] - villages[power[i]] + villages[power[i + 1]] - villages[s + 1])
			ans += min_sum
	print(ans)


t = int(input())
for z in range(t):
	n = int(input())
	s = input()
	(d, v) = ([], [])
	d = list(map(int, input().split()))
	for i in range(len(s)):
		if s[i] == '1':
			v.append(i)
	if n == 1:
		print(0)
		continue
	(a, ans) = (len(v), 0)
	for i in range(v[0] - 1, -1, -1):
		ans += d[i + 1] - d[i]
	for i in range(v[a - 1] + 1, n):
		ans += d[i] - d[i - 1]
	if a == 1:
		print(ans)
		continue
	for i in range(a - 1):
		(sum, m, l, r) = (0, 0, v[i], v[i + 1])
		for j in range(l, r):
			sum += d[j + 1] - d[j]
			m = max(m, d[j + 1] - d[j])
		ans += sum - m
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = input()
	y = input().split()
	d = []
	for i in range(n):
		d.append(int(y[i]))
	s = 0
	i = 0
	while a[i] == '0':
		s = s + (d[i + 1] - d[i])
		i = i + 1
	loc1 = i
	i = n - 1
	while a[i] == '0':
		s = s + (d[i] - d[i - 1])
		i = i - 1
	loc2 = i
	while loc1 < loc2:
		i = loc1
		flag = 0
		while a[i + 1] == '1':
			i = i + 1
			if i == loc2:
				flag = 1
				break
		if flag == 1:
			break
		j = i
		maximum = 0
		g = 0
		while a[j + 1] == '0':
			g = g + (d[j + 1] - d[j])
			if maximum < d[j + 1] - d[j]:
				maximum = d[j + 1] - d[j]
			j = j + 1
		g = g + (d[j + 1] - d[j])
		if maximum < d[j + 1] - d[j]:
			maximum = d[j + 1] - d[j]
		g = g - maximum
		s = s + g
		loc1 = j + 1
	print(s)
	t = t - 1


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	S = input()
	X = [int(i) for i in input().split()]
	i = 0
	total = 0
	temp = 0
	while i < N:
		if S[i] == '1':
			j = i + 1
			maxd = -float('inf')
			while j < N and S[j] == '0':
				temp += X[j] - X[j - 1]
				if X[j] - X[j - 1] > maxd:
					maxd = X[j] - X[j - 1]
				j += 1
			if j < N and S[j] == '1':
				temp += X[j] - X[j - 1]
				if X[j] - X[j - 1] > maxd:
					maxd = X[j] - X[j - 1]
				temp -= maxd
				total += temp
				temp = 0
			i = j
		else:
			i += 1
	correction = 0
	for i in range(N - 1):
		if S[i] == '1':
			break
		correction += X[i + 1] - X[i]
	total += temp + correction
	ans.append(total)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	e = [True if i == '1' else False for i in input().strip()]
	X = [int(i) for i in input().split()]
	ans = X[-1] - X[0]
	(p, q) = (None, None)
	for i in range(n):
		if e[i]:
			p = q
			q = i
			m = 0
			if p != None:
				for j in range(p, q):
					m = max(m, X[j + 1] - X[j])
			ans -= m
	print(ans)


t = int(input())
ans = []
for i in range(t):
	d = []
	light = []
	xcor = []
	n = int(input())
	ele = input()
	xcor.extend(map(int, input().split()))
	l = 0
	for j in range(n):
		if j != n - 1:
			d.append(xcor[j + 1] - xcor[j])
		if ele[j] == '1':
			light.append(j)
			l = l + 1
	sm = 0
	if l > 1:
		sm = sm + xcor[light[0]] - xcor[0] + xcor[n - 1] - xcor[light[l - 1]]
		for j in range(l - 1):
			if light[j + 1] - light[j] > 1:
				sm = sm + xcor[light[j + 1]] - xcor[light[j]] - max(d[light[j]:light[j + 1]])
	else:
		sm = sm + xcor[light[0]] - xcor[0] + xcor[n - 1] - xcor[light[0]]
	ans.append(sm)
for i in range(t):
	print(ans[i])


for t in range(int(input())):
	n = int(input())
	elec = list(input().strip())
	elec += ['0']
	city = i = 0
	x = [int(x) for x in input().split()]
	city = elec.count('1') - 1
	length = x[n - 1] - x[0]
	while elec[i] == '0':
		i += 1
	while city != 0:
		mx = 0
		i += 1
		while elec[i] == '0':
			if x[i] - x[i - 1] > mx:
				mx = x[i] - x[i - 1]
			i += 1
		if x[i] - x[i - 1] > mx:
			mx = x[i] - x[i - 1]
		length -= mx
		city -= 1
	print(length)


T = int(input())
while T:
	N = int(input())
	valid = input()
	arr = input().split(' ')
	e = []
	for i in range(0, len(arr)):
		arr[i] = int(arr[i])
		if valid[i] == '1':
			e.append(i)
	ans = arr[e[0]] - arr[0]
	ans = ans + arr[N - 1] - arr[e[len(e) - 1]]
	for i in range(0, len(e) - 1):
		left = arr[e[i]]
		right = arr[e[i + 1]]
		res = 1000000000
		for j in range(e[i], e[i + 1]):
			dist1 = arr[j] - left
			dist2 = right - arr[j + 1]
			res = min(res, dist1 + dist2)
		ans = ans + res
	print(ans)
	T = T - 1


t = int(input())
for _ in range(0, t):
	n = int(input())
	e = input()
	v = list(map(int, input().split()))
	sum = 0
	first = 0
	last = 0
	i = 0
	flag = False
	for i in range(0, n):
		if e[i] == '1':
			if flag == False:
				first = i
				flag = True
			last = i
	i = 0
	x = 0
	y = 0
	while i < first:
		sum += v[i + 1] - v[i]
		i += 1
	while i <= last and last != 0:
		sumf = 0
		suml = 0
		sum1 = 0
		sum2 = 0
		if e[i] == '1':
			i += 1
			x = i
			y = i
			continue
		elif e[i] == '0':
			first_flag = i - 1
			next_to__first_flag = i
			while e[i] != '1':
				if v[next_to__first_flag] - v[first_flag] <= v[i + 1] - v[i]:
					sum += v[next_to__first_flag] - v[first_flag]
					first_flag = i
					next_to__first_flag = i + 1
				else:
					sum += v[i + 1] - v[i]
				i += 1
	j = last + 1
	while j < n:
		sum += v[j] - v[j - 1]
		j += 1
	print(sum)


t = int(input())
ret = []
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	arr = list(map(int, input().split(' ')))
	l = []
	f = True
	for i in range(len(arr)):
		if s[i] == '1':
			if f:
				fr = i
				f = False
			l.append(i)
	r = []
	for i in range(1, len(l)):
		r.append([l[i - 1], l[i]])
	ans = 0
	for a in r:
		x = a[0]
		i = x + 1
		y = a[1]
		curr = arr[i] - arr[x]
		while i <= y:
			if arr[i] - arr[i - 1] > curr:
				curr = arr[i] - arr[i - 1]
			i += 1
		ans += abs(arr[y] - arr[x])
		ans -= curr
	ans += arr[fr] - arr[0]
	ans += arr[len(arr) - 1] - arr[l[len(l) - 1]]
	ret.append(ans)
for i in ret:
	print(i)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	marker = input()
	a = list(map(int, input().split()))
	sum = 0
	count = 0
	if marker[0] == '0':
		count += 1
		while marker[count] == '0':
			count += 1
		sum += a[count] - a[0]
	count += 1
	max = 0
	h1 = 0
	h2 = 0
	flag = 0
	for j in range(count, n):
		if marker[j] == '0':
			if marker[j - 1] == '1':
				h1 = j - 1
				x = a[j] - a[j - 1]
				if x > max:
					max = x
			elif marker[j - 1] == '0':
				x = a[j] - a[j - 1]
				if x > max:
					max = x
		elif marker[j] == '1':
			if marker[j - 1] == '0':
				h2 = j
				x = a[j] - a[j - 1]
				if x > max:
					max = x
				sum += a[h2] - a[h1] - max
				max = 0
	if marker[n - 1] == '0':
		sum += a[n - 1] - a[h1]
	ans.append(sum)
for x in ans:
	print(x)


for test in range(int(input())):
	n = int(input())
	s = str(input())
	ip = list(map(int, input().split()))
	a = []
	for i in range(n):
		if s[i] == '1':
			a.append(i)
	if len(a) == 1:
		ans = ip[-1] - ip[0]
	else:
		ans = ip[a[0]] - ip[0] + ip[-1] - ip[a[-1]]
		for i in range(len(a) - 1):
			m = 0
			ans += ip[a[i + 1]] - ip[a[i]]
			for j in range(a[i], a[i + 1]):
				if ip[j + 1] - ip[j] > m:
					m = ip[j + 1] - ip[j]
			ans -= m
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	x = [int(i) for i in input().split()]
	y = 0
	z = 0
	l = 0
	k = 0
	d = {}
	for i in range(len(s)):
		if s[i] == '1':
			d[y] = i
			y = y + 1
	ln = y
	if d[0] != 0:
		i = d[0]
		l = x[i] - x[0]
	for i in range(ln - 1):
		y = d[i]
		z = d[i + 1]
		max = -90
		for j in range(d[i] + 1, d[i + 1] + 1):
			if max < x[j] - x[j - 1]:
				max = x[j] - x[j - 1]
		l = l + (x[z] - x[y]) - max
	if d[ln - 1] != n - 1:
		i = d[ln - 1]
		l = l + (x[n - 1] - x[i])
	print(l)


MAX = 1 + 10 ** 9
T = int(input())
for t in range(T):
	N = int(input())
	E = input()
	X = list(map(int, input().strip().split()))
	ans = 0
	if E[0] == '0':
		E = E.lstrip('0')
		i = N - len(E)
		ans = ans + X[i] - X[0]
		X = X[i:]
		N -= i
	if E[-1] == '0':
		E = E.rstrip('0')
		i = N - len(E)
		ans = ans + X[-1] - X[N - i - 1]
		X = X[:N - i]
		N = N - i
	E = list(E)
	A = [0] * N
	B = [0] * N
	if N > 1:
		cur = 0
		for i in range(N):
			if E[i] == '1':
				cur = 0
			else:
				A[i] = A[i - 1] + X[i] - X[i - 1]
		for i in range(N - 1, -1, -1):
			if E[i] == '1':
				cur = 0
			else:
				B[i] = B[i + 1] + X[i + 1] - X[i]
		i = 0
		while i < N - 1:
			if E[i] == '1':
				mn = MAX
				i += 1
				while E[i] != '1':
					mn = min(mn, A[i - 1] + B[i])
					i += 1
				mn = min(mn, A[i - 1] + B[i])
				ans += mn
	print(ans)


import sys
f = sys.stdin
big = 10 ** 15

def solve(ee, x):
	ret = 0
	x0 = 0
	for i in range(len(ee)):
		if ee[i] == 0 or x0 > 0:
			dx = x[i] - x[i - 1] if i > 0 else big
			x0 = max(x0, dx)
			ret += dx
		if ee[i] == 1:
			ret -= x0
			x0 = 0
	return ret
t = int(f.readline())
for i in range(t):
	n = int(f.readline())
	ee = list(map(int, list(f.readline())[:-1]))
	x = list(map(int, f.readline().split()))
	print(solve(ee, x))


def func1():
	n = int(input())
	vs = list(input())
	ds = list(map(int, input().split()))
	wireLength = 0
	l = []
	found1 = False
	if vs[0] == '1':
		found1 = True
	for i in range(1, n):
		if vs[i] == '0':
			l.append(ds[i] - ds[i - 1])
			if i == n - 1:
				wireLength += sum(l)
		if vs[i] == '1':
			if vs[i - 1] == '0':
				l.append(ds[i] - ds[i - 1])
			if len(l) != 0:
				if found1:
					wireLength += sum(l) - max(l)
				else:
					wireLength += sum(l)
				l = []
			found1 = True
	return wireLength
nn = int(input())
ans = []
for _ in range(nn):
	ans.append(func1())
for i in ans:
	print(i)


test_cases = int(input())
for i in range(test_cases):
	n = int(input())
	vil = input()
	dis = input()
	dist = dis.split()
	(length, ind_zero) = (0, 0)
	if vil[0] == '0':
		zero = True
	else:
		zero = False
	for j in range(1, n):
		if vil[j] == '1':
			if zero == True:
				if ind_zero == 0:
					length += int(dist[j]) - int(dist[0])
				else:
					first_one = ind_zero - 1
					mini = int(dist[j]) - int(dist[ind_zero])
					for k in range(ind_zero, j):
						len1 = int(dist[k]) - int(dist[first_one])
						len2 = int(dist[j]) - int(dist[k + 1])
						if len1 + len2 < mini:
							mini = len1 + len2
					length += mini
				zero = False
		elif zero == False:
			zero = True
			ind_zero = j
	if zero == True:
		length += int(dist[n - 1]) - int(dist[ind_zero - 1])
	print(length)


T = int(input())
answers = []
for i in range(T):
	N = int(input())
	electricity = input()
	coordinates = list(map(int, input().split()))
	oneIndexes = []
	for j in range(0, len(electricity)):
		if electricity[j] == '1':
			oneIndexes.append(j)
	oneCount = len(oneIndexes)
	if oneCount == 1:
		total = 0
		for j in range(1, N):
			total = total + coordinates[j] - coordinates[j - 1]
		answers.append(total)
	else:
		total = 0
		total = total + coordinates[oneIndexes[0]] - coordinates[0]
		total = total + coordinates[N - 1] - coordinates[oneIndexes[-1]]
		for j in range(0, len(oneIndexes) - 1):
			start = oneIndexes[j]
			end = oneIndexes[j + 1]
			minans = pow(10, 9)
			for k in range(start, end):
				x = coordinates[k]
				y = coordinates[k + 1]
				ans = x - coordinates[start] + coordinates[end] - y
				if ans < minans:
					minans = ans
			total = total + minans
		answers.append(total)
for answer in answers:
	print(answer)


T = int(input())
while T > 0:
	N = int(input())
	mystr = input()
	user_input = input().split()
	ind = 1
	t = 1
	firstNum = mystr[0]
	mysum = 0
	if firstNum == '0':
		while mystr[t] != '1':
			t += 1
		mysum = int(user_input[t]) - int(user_input[0])
	while t < N:
		max_len = 0
		total_len = 0
		if mystr[t] == '0' and mystr[t - 1] == '1':
			while t < N and mystr[t] != '1':
				diff = int(user_input[t]) - int(user_input[t - 1])
				total_len += diff
				if diff > max_len:
					max_len = diff
				t += 1
			if t < N:
				diff = int(user_input[t]) - int(user_input[t - 1])
				total_len += diff
				if diff > max_len:
					max_len = diff
				mysum += total_len - max_len
			else:
				mysum += total_len
		else:
			t += 1
	print(mysum)
	T = T - 1


import operator
T = int(input())
out = []
for i in range(T):
	N = int(input())
	elec_str = input()
	has_elec = [False] * N
	has_road = [False] * (N - 1)
	x = list(map(int, input().split()))
	for i in range(N):
		has_elec[i] = elec_str[i] == '1'
	gap_sizes = {}
	for i in range(N - 1):
		gap_sizes[i] = x[i + 1] - x[i]
	sorted_gaps = sorted(gap_sizes.items(), key=operator.itemgetter(1))
	length = 0
	for (g, _) in sorted_gaps:
		if has_elec[g]:
			if has_elec[g + 1]:
				m = 1 + 1
			else:
				has_elec[g + 1] = True
				has_road[g] = True
				length = length + gap_sizes[g]
				h = g + 1
				while h < N - 1 and has_road[h] and (not has_elec[h + 1]):
					has_elec[h + 1] = True
					h = h + 1
		elif has_elec[g + 1]:
			has_elec[g] = True
			has_road[g] = True
			length = length + gap_sizes[g]
			h = g - 1
			while h >= 0 and has_road[h] and (not has_elec[h]):
				has_elec[h] = True
				h = h - 1
		else:
			has_road[g] = True
			length = length + gap_sizes[g]
	out.append(length)
	length = 0
for l in out:
	print(l)


def test(n, y, x):
	v = x[-1] - x[0]
	w = False
	record = 0
	for i in range(n):
		if i:
			delta = x[i] - x[i - 1]
			if delta > record:
				record = delta
		if y[i]:
			if w:
				v -= record
			else:
				w = True
			record = 0
	return v
T = int(input())
for t in range(T):
	n = int(input())
	y = list(map(int, list(input())))
	x = list(map(int, input().split()))
	print(test(n, y, x))


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	x_coords = [int(x) for x in input().split()]
	min_len = 0
	left_index = s.find('1')
	for i in range(left_index):
		min_len += x_coords[i + 1] - x_coords[i]
	right_index = s.rfind('1')
	for i in range(right_index + 1, n):
		min_len += x_coords[i] - x_coords[i - 1]
	right_index = s.find('1', left_index + 1)
	while True:
		if right_index == -1:
			break
		(i, j) = (left_index, right_index)
		while i != j - 1:
			diff_left = x_coords[i + 1] - x_coords[i]
			diff_right = x_coords[j] - x_coords[j - 1]
			if diff_left <= diff_right:
				min_len += diff_left
				i += 1
			else:
				min_len += diff_right
				j -= 1
		left_index = right_index
		right_index = s.find('1', right_index + 1)
	print(min_len)
	t -= 1


for t in range(int(input())):
	n = int(input())
	cin = [int(i) for i in list(input())]
	pos = [int(i) for i in input().split()]
	dist = [pos[i + 1] - pos[i] for i in range(n - 1)]
	charged = [cin.index(1)]
	while True:
		try:
			charged.append(cin.index(1, charged[-1] + 1))
		except:
			break
	total = pos[charged[0]] - pos[0] + pos[-1] - pos[charged[-1]]
	for (l, r) in zip(charged[:-1], charged[1:]):
		total += sum(dist[l:r]) - max(dist[l:r])
	print(total)


def minDist(start, end, a):
	temp = 0
	for i in range(start, end):
		temp = max(temp, a[i + 1] - a[i])
	return a[end] - a[start] - temp
t = int(input().strip())
for __ in range(t):
	n = int(input().strip())
	s = input().strip()
	a = [int(i) for i in input().strip().split()]
	l = []
	for i in range(len(s)):
		if s[i] == '1':
			l.append(i)
	ans = 0
	if 0 not in l:
		ans = ans + a[l[0]] - a[0]
	if n - 1 not in l:
		ans = ans - a[l[-1]] + a[-1]
	for i in range(len(l) - 1):
		ans = ans + minDist(l[i], l[i + 1], a)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	elec = input()
	coord = list(map(int, input().split()))
	sum1 = 0
	sum = 0
	temp1 = elec.index('1')
	for j in range(0, temp1):
		x = coord[j + 1] - coord[j]
		sum1 += x
	max = 0
	for j in range(temp1, n - 1):
		if elec[j] == '1':
			sum -= max
			max = 0
		x = coord[j + 1] - coord[j]
		sum += x
		if x > max:
			max = x
	if elec[n - 1] == '1':
		sum -= max
	print(sum1 + sum)


INT_MAX = 10 ** 18

def get_ans(start, end, maps):
	ans = INT_MAX
	for i in range(start, end):
		temp = maps[end] - maps[i + 1] + maps[i] - maps[start]
		if temp < ans:
			ans = temp
	return ans
t = int(input())
while t:
	n = int(input())
	status = input()
	maps = [int(loc) for loc in input().split()]
	ans = 0
	indices = [i for (i, x) in enumerate(status) if x == '1']
	ans += maps[indices[0]] - maps[0] + (maps[-1] - maps[indices[-1]])
	for i in range(len(indices) - 1):
		ans += get_ans(indices[i], indices[i + 1], maps)
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	arr = list(map(int, input().split()))
	ans = start = 0
	end = n - 1
	while s[end] == '0':
		end -= 1
	while s[start] == '0':
		start += 1
	i = start
	while i < end:
		j = i + 1
		while j <= end and s[j] == '0':
			j += 1
		maxdiff = 0
		for k in range(i + 1, j + 1):
			maxdiff = max(maxdiff, arr[k] - arr[k - 1])
		ans += arr[j] - arr[i] - maxdiff
		i = j
	ans += arr[start] - arr[0]
	ans += arr[-1] - arr[end]
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	x = [int(xi) for xi in input().split(' ')]
	res = 0
	first = False
	i = 0
	while i < n:
		if not first:
			if s[i] == '1':
				first = True
			else:
				res += x[i + 1] - x[i]
			i += 1
		elif not s[i] == '1':
			j = i + 1
			while j < n and (not s[j] == '1'):
				j += 1
			if j < n:
				mx = 0
				for k in range(i, j + 1):
					mx = max(mx, x[k] - x[k - 1])
					res += x[k] - x[k - 1]
				res -= mx
			else:
				for k in range(i, n):
					res += x[k] - x[k - 1]
			i = j
		else:
			i += 1
	print(res)


def calcWire(L, D):
	i = 0
	wire = 0
	while i < len(L):
		if L[i] == 0:
			leftPole = i
			while i < len(L) and L[i] == 0:
				i += 1
			rightPole = i
			if leftPole == 0:
				wire += D[rightPole] - D[0]
			elif rightPole > len(L) - 1:
				wire += D[rightPole - 1] - D[leftPole - 1]
			else:
				j = leftPole
				optimal = 10 ** 9 + 1
				while j < rightPole:
					if D[j] - D[leftPole - 1] + D[rightPole] - D[j + 1] < optimal:
						optimal = D[j] - D[leftPole - 1] + D[rightPole] - D[j + 1]
					j += 1
				wire += min(optimal, D[rightPole] - D[leftPole], D[rightPole - 1] - D[leftPole - 1])
		else:
			i += 1
	return wire
from sys import stdin
t = int(stdin.readline())
while t > 0:
	n = int(stdin.readline())
	L = [int(x) for x in stdin.readline().strip()]
	D = list(map(int, stdin.readline().split()))
	print(calcWire(L, D))
	t -= 1


from math import *
t = int(input())
for case in range(t):
	n = int(input())
	a = input()
	a = [int(a[i:i + 1]) for i in range(len(a))]
	d = [int(x) for x in input().split()]
	count = 0
	max_interval = 0
	start = a[0] == 0
	for i in range(1, n):
		if a[i] == 0 or a[i - 1] == 0:
			dist = d[i] - d[i - 1]
			count += dist
			if dist > max_interval:
				max_interval = dist
		if a[i] == 1:
			if not start:
				count -= max_interval
			max_interval = 0
			start = False
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	x = list(map(int, input().split()))
	ans = 0
	start = 0
	end = n - 1
	while s[start] == '0':
		start += 1
	while s[end] == '0':
		end -= 1
	ans += x[start] - x[0]
	ans += x[n - 1] - x[end]
	while start < end:
		temp = start
		start += 1
		largest = 0
		while s[start] == '0':
			largest = max(largest, x[start] - x[start - 1])
			start += 1
		largest = max(largest, x[start] - x[start - 1])
		ans += x[start] - x[temp] - largest
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	a = [int(v) for v in input()]
	x = [int(v) for v in input().split()]
	f = s = 0
	while f < n - 1:
		m = 0
		f1 = n - 1
		for i in range(f + 1, n):
			m = max(m, x[i] - x[i - 1])
			if a[i]:
				f1 = i
				break
		s = s + x[f1] - x[f]
		if a[f] and a[f1]:
			s = s - m
		f = f1
	print(s)


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	s = input()
	l = list(map(int, input().split()))
	l1 = []
	i = 1
	while i < n:
		l1 += [l[i] - l[i - 1]]
		i += 1
	k1 = s.index('1')
	c = s.count('1')
	ans = l[n - 1] - l[0]
	while c > 1:
		k2 = s.index('1', k1 + 1)
		ans -= max(l1[k1:k2])
		c -= 1
		k1 = k2
	print(ans)


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	light = [int(x) for x in input()]
	x = [int(x) for x in input().split()]
	i = 0
	while light[i] != 1:
		i += 1
	cost = x[i] - x[0]
	prev = i
	i += 1
	while i < N:
		Flag = True
		while light[i] != 1:
			if i == N - 1:
				cost += x[N - 1] - x[prev]
				Flag = False
				break
			else:
				i += 1
		if Flag:
			tmp = 10 ** 15
			for k in range(prev + 1, i):
				tmp = min(tmp, x[k] - x[prev] + x[i] - x[k + 1], x[k - 1] - x[prev] + x[i] - x[k])
			if tmp == 10 ** 15:
				tmp = 0
			cost += tmp
			prev = i
		i += 1
	print(cost)


import sys
T = int(sys.stdin.readline())
for i in range(T):
	N = int(sys.stdin.readline())
	A = sys.stdin.readline()
	B = list(map(int, sys.stdin.readline().split(' ')))
	Node = []
	for j in range(N):
		Node.append([int(A[j]), B[j]])
	wire = 0
	start = 0
	for j in range(len(Node)):
		if Node[j][0] == 1:
			start = j
			break
	wire = Node[start][1] - Node[0][1]
	end = 0
	for j in range(len(Node)):
		if Node[len(Node) - j - 1][0] == 1:
			end = len(Node) - j - 1
			break
	maxim = 0
	for j in range(start + 1, end + 1):
		wire += Node[j][1] - Node[j - 1][1]
		if maxim < Node[j][1] - Node[j - 1][1] and Node[j - 1] != 1:
			maxim = Node[j][1] - Node[j - 1][1]
		if Node[j][0] == 1:
			wire -= maxim
			maxim = 0
	wire += Node[len(Node) - 1][1] - Node[end][1]
	print(wire)