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

You are given 2 arrays W =  (W_{1}, W_{2}, .., W_{N}) and C =  (C_{1}, C_{2}, .., C_{N}) with N elements each. A range [l, r] is unique if all the elements C_{l}, C_{l+1}, .., C_{r} are unique (ie. no duplicates). The sum of the range is W_{l} +  W_{l+1} + ... + W_{r}.

You want to find an unique range with the maximum sum possible, and output this sum.

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

The first line of the input contains an integer T, denoting the number of test cases. The description of each testcase follows.
The first line of each test case contains a single integer N, denoting the size of the arrays.
The second line contains N space-separated integers : C_{1}, C_{2}, .., C_{N}.
The third line contains N space-separated integers : W_{1}, W_{2}, .., W_{N}.

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

For each testcase, output a single integer in a new line, which should be the maximum possible sum of an unique range.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000000$
$0 ≤ C_{i} < N$
$0 ≤ W_{i} ≤ 1000000000
$ $1 ≤ Sum of N over all test cases ≤ 1000000$

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

$Subtask #1 (30 points): Sum of N over all test cases ≤ 10000$
$Subtask #2 (70 points): Original constraints$

----- Sample Input 1 ------ 
1
5
0 1 2 0 2
5 6 7 8 2
----- Sample Output 1 ------ 
21
----- explanation 1 ------ 
The range [2, 4] is an unique range because (1, 2, 0) has no duplicates. Its sum is 6 + 7 + 8 = 21. This is the maximum possible, and hence is the answer.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Amortized analysis


Solutions:
from collections import defaultdict

def Test(n, c, w):
	d = {}
	for j in c:
		d[j] = 0
	(s, a, ans) = (0, 0, 0)
	for k in range(n):
		d[c[k]] += 1
		while d[c[k]] == 2:
			d[c[a]] -= 1
			s -= w[a]
			a += 1
		s += w[k]
		ans = max(ans, s)
	return ans
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	print(Test(n, c, w))


t = int(input())
for _ in range(t):
	n = int(input())
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	Ws = [W[0]]
	for i in range(1, n):
		Ws.append(Ws[-1] + W[i])
	S = [(0, 0)]
	R = [-1] * n
	R[C[0]] = 0
	ini = 0
	for i in range(1, n):
		a = C[i]
		if R[a] == -1:
			S.append((ini, i))
			R[a] = i
			pass
		elif R[a] < ini:
			S.append((ini, i))
			R[a] = i
		else:
			ini = R[a] + 1
			S.append((ini, i))
			R[a] = i
	Su = []
	for i in range(n):
		(a, b) = S[i]
		if a == 0:
			Su.append(Ws[b])
		else:
			Su.append(Ws[b] - Ws[a - 1])
	print(max(Su))


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	d = {}
	for j in c:
		d[j] = 0
	(s, a, ans) = (0, 0, 0)
	for k in range(n):
		d[c[k]] += 1
		while d[c[k]] == 2:
			d[c[a]] -= 1
			s -= w[a]
			a += 1
		s += w[k]
		ans = max(ans, s)
	print(ans)


tc = int(input())
for _ in range(tc):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	freq = {}
	for elem in c:
		freq[elem] = 0
	(sum, st, ans) = (0, 0, 0)
	for i in range(n):
		freq[c[i]] += 1
		while freq[c[i]] == 2:
			freq[c[st]] -= 1
			sum -= w[st]
			st += 1
		sum += w[i]
		ans = max(ans, sum)
	print(ans)


for k in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	vaish = list(map(int, input().split()))
	s = set([])
	st = 0
	s.add(c[0])
	maxk = vaish[0]
	sumk = vaish[0]
	for j in range(1, n):
		sumk += vaish[j]
		if c[j] not in s:
			s.add(c[j])
		else:
			while st < j and c[j] != c[st]:
				s.remove(c[st])
				st += 1
				sumk -= vaish[st - 1]
			st += 1
			sumk -= vaish[st - 1]
		if sumk > maxk:
			maxk = sumk
	print(maxk)


for _ in range(int(input())):
	N = int(input())
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	vi = [0] * N
	M = 0
	Sum = 0
	L = 0
	for i in range(N):
		if vi[C[i]] == 0:
			Sum += W[i]
			vi[C[i]] = 1
		else:
			M = max(M, Sum)
			Sum += W[i]
			k = C.index(C[i], L, i)
			Sum -= sum(W[L:k + 1])
			for j in range(L, k):
				vi[C[j]] = 0
			L = k + 1
	print(max(M, Sum))


red = lambda : list(map(int, input().split()))
from itertools import accumulate
for i in range(int(input())):
	n = int(input())
	l = red()
	wi = list(map(int, ('0 ' + input()).split()))
	wis = list(accumulate(wi))
	j = m = 0
	s = set()
	for i in range(n):
		while j < n and l[i] in s:
			s.remove(l[j])
			j += 1
		s.add(l[i])
		m = max(m, wis[i + 1] - wis[j])
	print(m)


def answer():
	c = [0] * (n + 1)
	(ans, i, j, s) = (0, 0, 0, 0)
	for i in range(n):
		while j < n and c[a[j]] == 0:
			c[a[j]] += 1
			s += w[j]
			j += 1
		ans = max(ans, s)
		if j == n:
			break
		c[a[i]] -= 1
		s -= w[i]
	return ans
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	w = list(map(int, input().split()))
	print(answer())


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	s = set([])
	start = 0
	s.add(c[0])
	maxi = w[0]
	sumi = w[0]
	for j in range(1, n):
		sumi += w[j]
		if c[j] not in s:
			s.add(c[j])
		else:
			while start < j and c[j] != c[start]:
				s.remove(c[start])
				start += 1
				sumi -= w[start - 1]
			start += 1
			sumi -= w[start - 1]
		if sumi > maxi:
			maxi = sumi
	print(maxi)


from math import *
from collections import defaultdict
R = lambda : list(map(int, input().split()))
MOD = 1000000007
for _ in range(int(input())):
	(n,) = R()
	c = R()
	w = R()
	d = defaultdict(lambda : -1)
	mx = 0
	(l, r) = (0, 0)
	sm = 0
	while l < n and r < n:
		idx = d[c[r]]
		if idx != -1:
			while l <= idx:
				d[c[l]] = -1
				sm -= w[l]
				l += 1
		else:
			sm += w[r]
			mx = max(mx, sm)
			d[c[r]] = r
			r += 1
	print(mx)


test = int(input())
for _ in range(test):
	input()
	ls = list(map(int, input().split()))
	l = list(map(int, input().split()))
	(s, i) = (set([ls[0]]), 0)
	c = mx = l[0]
	for j in range(1, len(ls)):
		while ls[j] in s:
			mx = max(mx, c)
			s.remove(ls[i])
			c -= l[i]
			i += 1
		s.add(ls[j])
		c += l[j]
	print(max(mx, c))


for _ in range(int(input())):
	input()
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	(s, i) = (set([C[0]]), 0)
	c = mx = W[0]
	for j in range(1, len(C)):
		while C[j] in s:
			mx = max(mx, c)
			s.remove(C[i])
			c -= W[i]
			i += 1
		s.add(C[j])
		c += W[j]
	print(max(mx, c))


def maxsegm(C, W):
	(d, s, t, i, r) = ({0: 0}, set(), 0, 0, 0)
	for j in range(len(C)):
		t += W[j]
		d[j + 1] = t
		while C[j] in s:
			s.remove(C[i])
			i += 1
		s.add(C[j])
		r = max(r, t - d[i])
	return r
for _ in range(int(input())):
	input()
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	print(maxsegm(C, W))


for t in range(int(input())):
	n = int(input())
	cost = list(map(int, input().strip().split()))
	weight = list(map(int, input().strip().split()))
	s = [0] * (n + 1)
	for i in range(n):
		s[i + 1] = s[i] + weight[i]
	ans = 0
	i = 0
	d = {}
	for j in range(n):
		if cost[j] not in d:
			d[cost[j]] = -1
		if d[cost[j]] >= i:
			i = d[cost[j]] + 1
		d[cost[j]] = j
		ans = max(ans, s[j + 1] - s[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	d = {}
	j = 0
	i = 0
	ans = 0
	mans = 0
	while i < n:
		if d.get(c[i], 0) == 0:
			ans += w[i]
			if ans > mans:
				mans = ans
			d[c[i]] = 1
			i += 1
		else:
			d[c[j]] -= 1
			ans -= w[j]
			j += 1
	print(mans)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	(prefix, maxi, l) = ([], 0, 0)
	unique = {}
	for i in range(n):
		if not i:
			prefix.append(w[i])
		else:
			prefix.append(prefix[i - 1] + w[i])
		if c[i] in unique:
			if unique[c[i]] >= l:
				l = unique[c[i]]
		maxi = max(maxi, prefix[i] if l == 0 else prefix[i] - prefix[l - 1])
		unique[c[i]] = i + 1
	print(maxi)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = [0]
	for i in b:
		x.append(x[-1] + i)
	ans = [0] * n
	d = {}
	c = 0
	for i in range(n):
		try:
			e = d[a[i]]
			c = x[i + 1] - x[e + 1]
			del d
			d = {}
			for j in range(e + 1, i + 1):
				d[a[j]] = j
			ans[i] = c
		except:
			d[a[i]] = i
			c += b[i]
			ans[i] = c
	print(max(ans))


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	visited = [0] * n
	loop_sum = 0
	max_sum = 0
	left_end = 0
	first_index = 0
	for i in range(n):
		if visited[c[i]] == 0:
			loop_sum += w[i]
			visited[c[i]] = 1
		else:
			max_sum = max(max_sum, loop_sum)
			loop_sum += w[i]
			first_index = c.index(c[i], left_end, i)
			loop_sum -= sum(w[left_end:first_index + 1])
			for j in range(left_end, first_index):
				visited[c[j]] = 0
			left_end = first_index + 1
	m = max(max_sum, loop_sum)
	print(m)


for _ in range(int(input())):
	N = int(input())
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	visited = [0] * N
	MaxSum = 0
	TestSum = 0
	L = 0
	for i in range(N):
		if visited[C[i]] == 0:
			TestSum += W[i]
			visited[C[i]] = 1
		else:
			MaxSum = max(MaxSum, TestSum)
			TestSum += W[i]
			k = C.index(C[i], L, i)
			TestSum -= sum(W[L:k + 1])
			for j in range(L, k):
				visited[C[j]] = 0
			L = k + 1
	MaxSum = max(MaxSum, TestSum)
	print(MaxSum)


def solution(C, W):
	low = 0
	k = {}
	k[C[low]] = 0
	maxi = W[0]
	ans = W[0]
	for i in range(1, len(C)):
		if C[i] not in k.keys():
			ans += W[i]
			k[C[i]] = i
		elif k[C[i]] >= low:
			j = low
			while j <= k[C[i]]:
				ans -= W[j]
				j += 1
			ans += W[i]
			low = k[C[i]] + 1
			k[C[i]] = i
		else:
			ans += W[i]
			k[C[i]] = i
		if maxi < ans:
			maxi = ans
	return maxi
T = int(input())
for t in range(T):
	n = int(input())
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	print(solution(C, W))


t = int(input())
while t != 0:
	n = int(input())
	c = input()
	c = [int(x) for x in c.split(' ')]
	w = input()
	w = [int(x) for x in w.split(' ')]
	arr = [0] * n
	max = w[0]
	sum = w[0]
	lo = 0
	hi = 1
	arr[c[0]] = 1
	while hi < n:
		if arr[c[hi]] == 0:
			arr[c[hi]] = 1
			sum = sum + w[hi]
			hi = hi + 1
		else:
			arr[c[lo]] = 0
			sum = sum - w[lo]
			lo = lo + 1
		if sum > max:
			max = sum
	print(max)
	t = t - 1


t = int(input())
for cs in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	found = [False for i in range(n)]
	max_sum = 0
	unique_sum = 0
	i = 0
	for j in range(n):
		if found[c[j]]:
			while c[i] != c[j]:
				found[c[i]] = False
				unique_sum -= w[i]
				i += 1
			unique_sum -= w[i]
			i += 1
		found[c[j]] = True
		unique_sum += w[j]
		max_sum = max(max_sum, unique_sum)
	print(max_sum)


t = int(input())
for test in range(t):
	n = int(input())
	c_array = [i for i in map(int, input().split())]
	w_array = [i for i in map(int, input().split())]
	seen = [False for i in range(n)]
	result_sum = 0
	i = 0
	j = 0
	max_sum = 0
	while j < n:
		if seen[c_array[j]] == True:
			while c_array[i] != c_array[j]:
				result_sum -= w_array[i]
				seen[c_array[i]] = False
				i += 1
			seen[c_array[i]] = False
			result_sum -= w_array[i]
			i += 1
		seen[c_array[j]] = True
		result_sum += w_array[j]
		if max_sum < result_sum:
			max_sum = result_sum
		j += 1
	print(max_sum)


hash = []
for i in range(1000000):
	hash.append(0)
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	w = list(map(int, input().split()))
	for i in range(n):
		hash[i] = 0
	maxx = max(w)
	l = 0
	r = 1
	s = w[0]
	hash[a[0]] += 1
	if r < n:
		hash[a[r]] += 1
		s += w[r]
	while l < n and r < n:
		if l == r:
			r += 1
			if r < n:
				hash[a[r]] += 1
				s += w[r]
		elif hash[a[r]] < 2 and hash[a[l]] < 2:
			if maxx < s:
				maxx = s
			r += 1
			if r < n:
				hash[a[r]] += 1
				s += w[r]
		else:
			s -= w[l]
			hash[a[l]] -= 1
			l += 1
	print(maxx)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	ans = [False] * n
	m = 0
	s = 0
	l = 0
	r = 0
	while True:
		while r < n and (not ans[c[r]]):
			s += w[r]
			ans[c[r]] = True
			r += 1
		m = max(m, s)
		if r == n:
			break
		while ans[c[r]]:
			ans[c[l]] = False
			s -= w[l]
			l += 1
	print(m)


for t in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	pres = [0]
	for i in range(n):
		pres.append(pres[-1] + w[i])
	(i, j) = (0, 1)
	ma = 0
	x = {c[0]}
	while i < n:
		if j < n and c[j] not in x:
			x.add(c[j])
			j += 1
		else:
			x.remove(c[i])
			i += 1
		diff = pres[j] - pres[i]
		if ma < diff:
			ma = diff
	print(ma)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	a = [0] * 1000001
	i = j = sum = ans = 0
	while i < n:
		while j < n and a[c[j]] == 0:
			a[c[j]] = 1
			sum += w[j]
			j += 1
		ans = max(sum, ans)
		a[c[i]] = 0
		sum -= w[i]
		i += 1
	print(max(ans, sum))


t = int(input())
for x in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	u = []
	s = 0
	st = set()
	i = 0
	d = dict()
	while i < n:
		if c[i] not in st:
			s = s + w[i]
			st.add(c[i])
			d[c[i]] = i
			i = i + 1
		else:
			u.append(s)
			s = 0
			i = d[c[i]] + 1
			st.clear()
			d.clear()
	u.append(s)
	print(max(u))


cases = int(input())
for x in range(cases):
	nums = int(input())
	array = list(map(int, input().split()))
	weights = [0] + list(map(int, input().split()))
	dictionary = {}
	prev = 0
	score = 0
	for index in range(nums):
		weights[index + 1] += weights[index]
		item = array[index]
		dict_index = dictionary.get(item)
		if dict_index is not None:
			prev = max(prev, dict_index)
		score = max(score, weights[index + 1] - weights[prev])
		dictionary[item] = index + 1
	print(score)


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	res = 0
	d1 = {}
	sum1 = 0
	s1 = []
	max1 = 0
	k = -1
	for j in range(n):
		sum1 += l2[j]
		s1.append(sum1)
		if d1.get(l1[j], -1) == -1:
			if k >= 0:
				res = s1[j] - s1[k]
			else:
				res = s1[j]
			d1[l1[j]] = j
		else:
			if d1[l1[j]] > k:
				k = d1[l1[j]]
			res = s1[j] - s1[k]
			d1[l1[j]] = j
		if res > max1:
			max1 = res
	print(max1)


t = int(input())
for t1 in range(t):
	n = int(input())
	a = []
	b = []
	a = list(map(int, input().strip().split(' ')))
	b = list(map(int, input().strip().split(' ')))
	s = 0
	e = 0
	max = 0
	sum = 0
	bucket = [0] * n
	for i in range(n):
		if bucket[a[i]] == 0:
			e = i
			bucket[a[i]] = 1
			sum = sum + b[i]
		else:
			if sum > max:
				max = sum
			while s <= e:
				bucket[a[s]] = 0
				sum = sum - b[s]
				s = s + 1
				if a[s - 1] == a[i]:
					bucket[a[i]] = 1
					e = i
					sum = sum + b[i]
					break
	if sum > max:
		max = sum
	print(max)


t = int(input())
for _ in range(t):
	n = int(input())
	indexes = list(map(int, input().split()))
	values = list(map(int, input().split()))
	leftsum = [-1] * n
	lastindex = [-1] * n
	startindex = 0
	tempindex = 0
	maxsum = 0
	tempsum = 0
	totalsum = 0
	for i in range(n):
		if lastindex[indexes[i]] >= tempindex:
			tempsum = totalsum - leftsum[indexes[i]] + values[i]
			if tempsum >= maxsum:
				maxsum = tempsum
				startindex = i
			tempindex = lastindex[indexes[i]] + 1
			totalsum += values[i]
			leftsum[indexes[i]] = totalsum
			lastindex[indexes[i]] = i
		else:
			tempsum += values[i]
			totalsum += values[i]
			leftsum[indexes[i]] = totalsum
			lastindex[indexes[i]] = i
			if tempsum > maxsum:
				maxsum = tempsum
	print(maxsum)


T = int(input())
for eachCase in range(T):
	N = int(input())
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	seen = [False] * N
	L = R = 0
	maxSum = currentSum = 0
	while True:
		while R < N and (not seen[C[R]]):
			currentSum += W[R]
			seen[C[R]] = True
			R += 1
		maxSum = max(currentSum, maxSum)
		if R == N:
			break
		while seen[C[R]]:
			seen[C[L]] = False
			currentSum -= W[L]
			L += 1
	print(maxSum)


for t in range(int(input())):
	n = int(input())
	ar2 = input().split()
	x = {}
	for i in range(n):
		ar2[i] = int(ar2[i])
		x[ar2[i]] = False
	ar = input().split()
	ar[0] = int(ar[0])
	for i in range(1, n):
		ar[i] = int(ar[i])
		ar[i] = ar[i - 1] + ar[i]
	ar.append(0)
	i = j = 0
	ans = tans = 0
	while i < n:
		while j < n and x[ar2[j]] == False:
			x[ar2[j]] = True
			tans = ar[j] - ar[i - 1]
			ans = max(tans, ans)
			j = j + 1
		x[ar2[i]] = False
		i = i + 1
	print(ans)


def find(n, c, w):
	big = 0
	sum = 0
	sum1 = 0
	j = 0
	a = [0 for i in range(n)]
	m = {}
	x = -1
	while j < n:
		sum1 += w[j]
		a[j] = sum1
		if c[j] not in m:
			if x >= 0:
				sum = a[j] - a[x]
			else:
				sum = a[j]
			m[c[j]] = j
		else:
			if m[c[j]] > x:
				x = m[c[j]]
			sum = a[j] - a[x]
			m[c[j]] = j
		if sum > big:
			big = sum
		j += 1
	return big
t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	print(find(n, c, w))


t = int(input())
while t:
	t -= 1
	n = int(input())
	C = [int(x) for x in input().strip().split()]
	W = [int(x) for x in input().strip().split()]
	C_location = []
	latest_location = []
	for i in range(0, n):
		C_location.append(False)
		latest_location.append(-1)
	maxm_unique_sum = -1
	sum_until = []
	prev_summ = 0
	for val in W:
		prev_summ += val
		sum_until.append(prev_summ)
	i = 0
	start = i
	while i < n:
		while i < n:
			if C_location[C[i]]:
				if latest_location[C[i]] < start:
					latest_location[C[i]] = i
					i += 1
					continue
				break
			latest_location[C[i]] = i
			C_location[C[i]] = True
			i += 1
		end = i - 1
		prev_summ = sum_until[end] - sum_until[start] + W[start]
		if prev_summ > maxm_unique_sum:
			maxm_unique_sum = prev_summ
		if i < n:
			start = latest_location[C[i]] + 1
			latest_location[C[i]] = i
		i += 1
	print(maxm_unique_sum)


for _ in range(int(input())):
	N = int(input())
	C = list(map(int, input().split()))
	W = list(map(int, input().split()))
	sumW = [0] * N
	sumW[0] = W[0]
	for i in range(1, N):
		sumW[i] = W[i] + sumW[i - 1]
	l = 0
	r = 0
	maxsum = -1
	status = [None] * N
	while l < N and r < N:
		if status[C[r]] == None:
			status[C[r]] = r
			r += 1
		else:
			tempsum = sumW[r - 1] - sumW[l] + W[l]
			if tempsum > maxsum:
				maxsum = tempsum
			for i in range(l, status[C[r]]):
				status[C[i]] = None
			l = status[C[r]] + 1
			status[C[r]] = None
	tempsum = sumW[r - 1] - sumW[l] + W[l]
	if tempsum > maxsum:
		maxsum = tempsum
	print(maxsum)


t = int(input())
for i in range(t):
	n = int(input())
	c = [int(x) for x in input().split()]
	w = [int(x) for x in input().split()]
	s = []
	for i in range(n):
		if i == 0:
			s.append(w[0])
		else:
			s.append(s[-1] + w[i])
	l = 0
	r = 0
	j = 0
	su = 0
	mas = 0
	vis = []
	for i in range(n):
		vis.append(0)
	for i in range(n):
		vis[c[l]] = 0
		l = i
		while True:
			if r == n:
				break
			if vis[c[r]] == 1:
				break
			vis[c[r]] = 1
			r = r + 1
		r -= 1
		if l == 0:
			su = s[r]
		else:
			su = s[r] - s[l - 1]
		if mas < su:
			mas = su
		r += 1
	print(mas)


for _ in range(int(input())):
	n = int(input())
	c = [int(i) for i in input().split()]
	w = [int(i) for i in input().split()]
	b = [-1 for i in range(n)]
	sry = [w[0]]
	for i in range(1, n):
		sry.append(sry[-1] + w[i])
	ans = 0
	sp = 0
	d = 0
	i = 0
	while i < n:
		if b[c[i]] == -1:
			b[c[i]] = i
			d += w[i]
			ans = max(ans, d)
		else:
			l = b[c[i]]
			d -= sry[l]
			if sp > 0:
				d += sry[sp - 1]
			d += w[i]
			ans = max(ans, d)
			while sp < l:
				b[c[sp]] = -1
				sp += 1
			sp += 1
			b[c[i]] = i
		i += 1
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = temp = 0
	d = [0] * n
	i = j = k = 0
	while i < n:
		while j < n and d[a[j]] == 0:
			d[a[j]] = 1
			temp += b[j]
			j += 1
		ans = max(ans, temp)
		f = 0
		while k < n and j < n and (a[j] != a[k]):
			d[a[k]] = 0
			temp -= b[k]
			f = 1
			k += 1
		if k < n:
			temp -= b[k]
		if j < n:
			temp += b[j]
			ans = max(ans, temp)
		i += 1
		k += 1
		j += 1
	print(ans)


from collections import deque

def _in():
	return list(map(int, input().split()))
t = int(input())
while t:
	t -= 1
	n = int(input())
	c = _in()
	w = _in()
	a = deque([])
	b = deque([])
	s = set()
	ans = 0
	local = 0
	for i in range(n):
		if c[i] not in s:
			a.append(c[i])
			b.append(w[i])
			s.add(c[i])
			local += w[i]
			ans = max(ans, local)
		else:
			r = -1
			while c[i] != r:
				r = a.popleft()
				s.discard(r)
				local -= b.popleft()
			a.append(c[i])
			s.add(c[i])
			b.append(w[i])
			local += w[i]
			ans = max(ans, local)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = list(map(int, input().split()))
	ans = 0
	s = []
	s.append(w[0])
	for i in w[1:]:
		s.append(s[-1] + i)
	f = [-1] * (n + 1)
	cs = 0
	t = 0
	for i in range(n):
		if f[c[i]] == -1 or f[c[i]] < t:
			cs += w[i]
			f[c[i]] = i
		else:
			cs = s[i] - s[f[c[i]]]
			t = f[c[i]] + 1
			f[c[i]] = i
		if cs > ans:
			ans = cs
	print(ans)


for tt in range(int(input())):
	n = int(input())
	m = {}
	for i in range(n):
		m[i] = -1
	c = [int(i) for i in input().split()]
	w = [int(i) for i in input().split()]
	ans = 0
	j = 0
	i = 0
	sm = 0
	while i < n:
		if m[c[i]] != -1:
			h = m[c[i]]
			for k in range(j, h + 1):
				m[c[k]] = -1
				sm -= w[k]
			j = h + 1
		m[c[i]] = i
		sm += w[i]
		ans = max(sm, ans)
		i += 1
	print(ans)


t = int(input())
for u in range(t):
	prefix = []
	n = int(input())
	c = input().split()
	for val in range(len(c)):
		c[val] = int(c[val])
	w = input().split()
	for val in range(len(w)):
		w[val] = int(w[val])
	prefix.append(0)
	for val in range(len(w)):
		prefix.append(prefix[val] + w[val])
	D = {}
	q = []
	start = 0
	end = 0
	maxsum = 0
	while start < n:
		while start < n and c[start] not in D:
			q.append(c[start])
			D[c[start]] = 1
			start += 1
		if prefix[start] - prefix[end] > maxsum:
			maxsum = prefix[start] - prefix[end]
		if start == n:
			break
		while q[0] != c[start]:
			del D[q.pop(0)]
			end += 1
		del D[q.pop(0)]
		end += 1
	print(maxsum)


import io
import sys

def test_data():
	return io.StringIO('1\n5\n0 1 2 0 2\n5 6 7 8 2')

def get_input(source):
	with source as lines:
		t = int(next(lines))
		for _ in range(t):
			n = int(next(lines))
			c = list(map(int, next(lines).split(' ')))
			w = list(map(int, next(lines).split(' ')))
			yield (n, c, w)

def calc(n, c, w):
	left = 0
	right = 0
	cur = set()
	ans = -1
	cur_sum = 0
	while right != len(c):
		if c[right] in cur:
			ans = max(ans, cur_sum)
			cur.remove(c[left])
			cur_sum -= w[left]
			left += 1
		else:
			cur.add(c[right])
			cur_sum += w[right]
			right += 1
	ans = max(ans, cur_sum)
	return ans
inp = test_data() if '-test' in sys.argv else sys.stdin
for args in get_input(inp):
	print(calc(*args))


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

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

def map_string():
	return input().split()
for _ in range(int(input())):
	n = int(input())
	c = list_input()
	w = list_input()
	last = [0] * (n + 5)
	pref = [0]
	for i in w:
		pref.append(pref[-1] + i)
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		dp[i] = min(dp[i - 1] + w[i - 1], pref[i] - pref[last[c[i - 1]]])
		last[c[i - 1]] = i
	print(max(dp))