Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef is playing a game with his brother Chefu. Before the game begins, C cards are placed on a table. Each card has a number written on it; since C can be very large, these numbers are described by two sequences A and D. Each of these sequences has length N; for each i (1 ≤ i ≤ N), D_{i} cards, each with number A_{i} written on it, are placed on the table. Therefore, C is equal to the sum of elements of D. Note that the elements of A don't have to be unique.

You are also given a sequence B with length K. The game will last for exactly K rounds numbered 1 through K. The players alternate turns — Chef plays on odd-numbered turns and his brother on even-numbered turns. In the i-th round, the current player must select B_{i} cards currently lying on the table, keep these cards on the table and discard all other cards.

Chef's goal is to maximize the sum of numbers written on cards that remain on the table after the last round, while Chefu's goal is minimize this sum. What will be the sum of numbers written on cards remaining on the table if both players play optimally?

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

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and K.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N}.
The third line contains N space-separated integers D_{1}, D_{2}, ..., D_{N}.
The fourth line contains K space-separated integers B_{1}, B_{2}, ..., B_{K}.

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

For each test case, print a single line containing one integer — the sum of numbers on cards that remain on the table at the end of the game.

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

$1 ≤ T ≤ 100$
$1 ≤ N, K ≤ 100,000$
$1 ≤ sum of N over all test cases ≤ 100,000$
$1 ≤ sum of K over all test cases ≤ 100,000$
$1 ≤ A_{i}, D_{i} ≤ 1,000,000 for each valid i$
$1 ≤ B_{i} ≤ C for each valid i$
$B_{i+1} < B_{i} for each valid i$

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

Subtask #1 (20 points): 

$D_{i} = 1 for each valid i$
$sum of N over all test cases ≤ 1,000$
$sum of K over all test cases ≤ 1,000$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
1
4 2
1 2 3 4
2 2 2 2
6 3
----- Sample Output 1 ------ 
7
----- explanation 1 ------ 
Example case 1: The cards that are on table initially are 1, 1, 2, 2, 3, 3, 4, 4 Chef in his turn should select 6 cards to keep and discard the rest, so he will keep 2, 2,
3, 3, 4, 4 after that Chefu should keep 3 cards and discard the rest, so he will keep 2, 2,
3 after that the game ends and sum of cards remained on the table is 2 + 2 + 3 = 7

Difficulty: HARD
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	arr = [[int(i)] for i in input().split()]
	l = input().split()
	value = 0
	for i in range(n):
		arr[i].append(int(l[i]))
		value += int(l[i])
	arr.sort()
	ans = [value]
	move = list(map(int, input().split()))
	for i in range(k):
		if i % 2 == 0:
			ans.append(ans[-1] - move[i] + 1)
		else:
			ans.append(ans[-1] + move[i] - 1)
	p = 0
	x = max(ans[-1], ans[-2])
	y = min(ans[-1], ans[-2])
	index1 = index2 = None
	for i in range(len(arr)):
		p += arr[i][1]
		if p >= y and index1 == None:
			index1 = i
			x1 = p - y + 1
		if p >= x:
			index2 = i
			x2 = x - p + arr[i][1]
			break
	if index1 == index2:
		v = arr[index1][0] * (x - y + 1)
	else:
		v = arr[index1][0] * x1 + arr[index2][0] * x2
		for i in range(index1 + 1, index2):
			v += arr[i][0] * arr[i][1]
	print(v)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	z = input().split()
	a = list(map(int, z[:n]))
	z = input().split()
	d = list(map(int, z[:n]))
	z = input().split()
	b = list(map(int, z[:k]))
	dis = [p - c for (c, p) in zip(b, [sum(d)] + b)]
	lo = sum(dis[::2])
	hi = sum(dis[1::2])
	p = [[ai, di] for (ai, di) in zip(a, d)]
	p.sort()
	for px in range(n):
		if p[px][1] >= lo:
			p[px][1] -= lo
			lo = 0
			break
		else:
			lo -= p[px][1]
			p[px][1] = 0
	for px in range(n - 1, -1, -1):
		if p[px][1] >= hi:
			p[px][1] -= hi
			hi = 0
			break
		else:
			hi -= p[px][1]
			p[px][1] = 0
	print(sum((pi[0] * pi[1] for pi in p)))


T = int(input())
for testCase in range(T):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	D = list(map(int, input().split()))
	C = []
	n = 0
	for i in range(N):
		C.append([A[i], D[i]])
		n += D[i]
	C.sort()
	B = list(map(int, input().split()))
	right = 0
	left = 0
	for i in range(K):
		if i % 2 == 0:
			left += n - B[i]
		else:
			right += n - B[i]
		n = B[i]
	i = 0
	while left > 0:
		if left <= C[i][1]:
			C[i][1] -= left
			left = 0
		else:
			left -= C[i][1]
			C[i][1] = 0
			i += 1
	i = N - 1
	while right > 0:
		if right <= C[i][1]:
			C[i][1] -= right
			right = 0
		else:
			right -= C[i][1]
			C[i][1] = 0
			i -= 1
	ans = 0
	for i in range(N):
		ans += C[i][0] * C[i][1]
	print(ans)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = list(map(list, zip(a, d)))
	l = sorted(l, key=lambda x: x[0])
	s1 = 0
	s2 = 0
	s = 0
	tot = sum(d)
	for j in range(k):
		if j % 2 == 0:
			s1 += tot - b[j]
		else:
			s2 += tot - b[j]
		tot = b[j]
	for j in range(n):
		s += a[j] * d[j]
	j = 0
	sj = 0
	while True:
		sj += l[j][1]
		if sj <= s1:
			s -= l[j][0] * l[j][1]
		elif sj - l[j][1] <= s1:
			x = s1 - sj + l[j][1]
			s -= l[j][0] * x
			break
		else:
			break
		j += 1
	j = -1
	sj = 0
	while True:
		sj += l[j][1]
		if sj <= s2:
			s -= l[j][0] * l[j][1]
		elif sj - l[j][1] <= s2:
			x = s2 - sj + l[j][1]
			s -= l[j][0] * x
			break
		else:
			break
		j -= 1
	print(s)


outputs = []
T = int(input())
for i in range(0, T):
	n = input().split()
	a = input().split()
	d = input().split()
	b = input().split()
	a = list(map(int, a))
	d = list(map(int, d))
	(N, K) = (int(n[0]), int(n[1]))
	b = list(map(int, b))
	ncards = sum(d)
	list1 = []
	z = 0
	z2 = 0
	for i in range(0, N):
		list1.append([a[i], d[i]])
	list1.sort()
	chef = ncards - b[0]
	chefu = 0
	for i in range(0, K - 1):
		if i % 2 == 0:
			chefu += b[i] - b[i + 1]
		else:
			chef += b[i] - b[i + 1]
	z = 0
	i = 0
	while z <= ncards:
		z += list1[i][1]
		if z == chef:
			list1 = list1[i + 1:]
			break
		elif z > chef:
			list1[i][1] = z - chef
			list1 = list1[i:]
			break
		i += 1
	z = 0
	i = len(list1) - 1
	while z <= ncards:
		z += list1[i][1]
		if z == chefu:
			list1 = list1[:i]
			break
		elif z > chefu:
			list1[i][1] = z - chefu
			list1 = list1[:i + 1]
			break
		i -= 1
	ans = 0
	for i in range(0, len(list1)):
		ans += list1[i][0] * list1[i][1]
	outputs.append(ans)
for i in range(0, T):
	print(outputs[i])


T = int(input())
for i in range(0, T):
	(N, K) = map(int, input().split())
	A = [int(x) for x in input().split()]
	D = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	L = sorted(zip(A, D))
	L = L[::-1]
	for j in range(0, len(L)):
		L[j] = list(L[j])
	if K % 2 != 0:
		B.append(B[-1])
	sum = 0
	for j in range(0, len(B), 2):
		sum = sum + (B[j] - B[j + 1])
	sumu = 0
	for j in range(0, len(L)):
		sumu = sumu + L[j][1]
		if sumu >= sum:
			L[j][1] = sumu - sum
			L = L[j:]
			break
	sumu2 = 0
	for j in range(0, len(L)):
		sumu2 = sumu2 + L[j][1]
		if sumu2 >= B[-1]:
			L[j][1] = L[j][1] - sumu2 + B[-1]
			L = L[:j + 1]
			break
	sumu3 = 0
	for j in range(0, len(L)):
		sumu3 = sumu3 + L[j][0] * L[j][1]
	print(sumu3)


t = int(input())
for z in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	big = [[a[i], d[i]] for i in range(n)]
	big.sort()
	left = 0
	right = n - 1
	num_cards = sum(d)
	for z in range(k):
		target = b[z]
		if z % 2 == 0:
			idx = right
			while True:
				if num_cards >= target + big[left][1]:
					num_cards -= big[left][1]
					left += 1
				else:
					big[left][1] -= num_cards - target
					num_cards = target
					break
		else:
			idx = left
			while True:
				if num_cards >= target + big[right][1]:
					num_cards -= big[right][1]
					right -= 1
				else:
					big[right][1] -= num_cards - target
					num_cards = target
					break
	ans = 0
	for i in range(left, right + 1):
		ans += big[i][0] * big[i][1]
	print(ans)


def length(t1, t2):
	(a, b) = t1
	(c, d) = t2
	return max(0, min(d, b) - max(a, c))
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	D = list(map(int, input().split()))
	C = sum(D)
	B = list(map(int, input().split()))
	(evs, ods) = (0, 0)
	B = [C] + B
	for i in range(1, len(B)):
		if i % 2 == 0:
			evs += B[i - 1] - B[i]
		else:
			ods += B[i - 1] - B[i]
	arr = [(A[i], D[i]) for i in range(N)]
	arr.sort(key=lambda x: x[0])
	endpts = [0 for i in range(N)]
	s = 0
	for i in range(len(D)):
		endpts[i] = (s, s + arr[i][1])
		s += arr[i][1]
	ans = 0
	for k in range(N):
		ans += arr[k][0] * length(endpts[k], (ods, C - evs))
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	crd = 0
	for i in range(len(a)):
		arr += [[a[i], d[i]]]
		crd += d[i]
	arr.sort(key=lambda x: x[0])
	for crawl in range(k):
		todo = crd - b[crawl]
		if crawl % 2 != 0:
			init = len(arr) - 1
			while todo != 0:
				if arr[init][1] > todo:
					arr[init][1] -= todo
					todo = 0
				else:
					todo -= arr[init][1]
					del arr[init]
					init -= 1
		else:
			init = 0
			while todo != 0:
				if arr[init][1] > todo:
					arr[init][1] -= todo
					todo = 0
				else:
					todo -= arr[init][1]
					del arr[init]
		crd = b[crawl]
	flag = 0
	for walk in range(len(arr)):
		flag += arr[walk][0] * arr[walk][1]
	print(flag)


import sys

def main(N, K):
	A = sys.stdin.readline().split()
	D = sys.stdin.readline().split()
	AD = [[int(A[y]) if x == 0 else int(D[y]) for x in range(2)] for y in range(len(A))]
	B = sys.stdin.readline().split()
	B = [int(x) for x in B]
	AD = sorted(AD, key=lambda l: l[0])
	A = [AD[i][0] for i in range(len(A))]
	D = [AD[i][1] for i in range(len(D))]
	sumaD = sum(D)
	B_par = [B[2 * i] for i in range((K + 1) // 2)]
	B_impar = [B[2 * i + 1] for i in range(K // 2)]
	limMin = sumaD - sum(B_par) + sum(B_impar[0:len(B_impar) - (K + 1) % 2])
	limMax = sumaD - sum(B_par[0:len(B_par) - K % 2]) + sum(B_impar[0:len(B_impar)])
	(A, D) = maximosLista(sumaD - limMin, A, D)
	(A, D) = minimosLista(limMax - limMin, A, D)
	suma = sum((i[0] * i[1] for i in zip(A, D)))
	print(suma)

def maximosLista(B_i, A, D):
	eligiendo = True
	primerIndice = len(A) - 1
	primerD = 0
	while eligiendo:
		if B_i == 0:
			eligiendo = False
		elif D[primerIndice] >= B_i:
			primerD = B_i
			eligiendo = False
		elif D[primerIndice] < B_i:
			B_i += -D[primerIndice]
			primerIndice += -1
	if primerD != 0:
		A = [A[x] for x in range(primerIndice, len(A))]
		D = [D[x] if x != primerIndice else primerD for x in range(primerIndice, len(D))]
	else:
		A = []
		D = []
	return (A, D)

def minimosLista(B_i, A, D):
	eligiendo = True
	ultimoIndice = 0
	ultimoD = 0
	while eligiendo:
		if B_i == 0:
			eligiendo = False
		elif D[ultimoIndice] >= B_i:
			ultimoD = B_i
			eligiendo = False
		elif D[ultimoIndice] < B_i:
			B_i += -D[ultimoIndice]
			ultimoIndice += 1
	if ultimoD != 0:
		A = [A[x] for x in range(ultimoIndice + 1)]
		D = [D[x] if x != ultimoIndice else ultimoD for x in range(0, ultimoIndice + 1)]
	else:
		A = []
		D = []
	return (A, D)
casos = int(sys.stdin.readline())
for i in range(casos):
	listaIn = sys.stdin.readline().split()
	N = int(listaIn[0])
	K = int(listaIn[1])
	main(N, K)


from operator import itemgetter
T = int(input())
for t in range(T):
	[n, k] = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = 0
	for x in d:
		c += x
	gg = [[a[i], d[i]] for i in range(n)]
	gg = sorted(gg, key=itemgetter(0))
	even = 0
	odd = 0
	for (i, x) in enumerate(b):
		if i % 2 == 0:
			odd += c - x
			c = x
		else:
			even += c - x
			c = x
	l = len(gg)
	while even > 0 and l > 0:
		if gg[l - 1][1] < even:
			even -= gg[l - 1][1]
			l -= 1
		else:
			gg[l - 1][1] -= even
			gg = gg[:l - len(gg)]
			even = 0
	i = 0
	l = len(gg)
	while odd > 0 and i < l:
		if gg[i][1] < odd:
			odd -= gg[i][1]
			i += 1
		else:
			gg[i][1] -= odd
			gg = gg[i:]
			odd = 0
	res = 0
	for x in gg:
		res += x[0] * x[1]
	print(res)


t = int(input().strip())
while t > 0:
	(n, k) = [int(x) for x in input().strip().split(' ')]
	a = [int(x) for x in input().strip().split(' ')]
	d = [int(x) for x in input().strip().split(' ')]
	b = [int(x) for x in input().strip().split(' ')]
	p = list(map(list, zip(a, d)))
	tot = sum(d)
	p.sort(key=lambda x: (x[0], x[1]))
	j = 0
	lenb = len(b)
	lenp = len(p)
	start = 0
	end = lenp - 1
	while j < lenb:
		k = tot - b[j]
		tot -= k
		if j % 2 == 0:
			while start < lenp:
				z = k
				k -= p[start][1]
				if k == 0:
					start += 1
					break
				if k > 0:
					start += 1
				else:
					p[start][1] -= z
					break
		else:
			while end >= 0:
				z = k
				k -= p[end][1]
				if k == 0:
					end -= 1
					break
				if k > 0:
					end -= 1
				else:
					p[end][1] -= z
					break
		j += 1
	tsum = 0
	if start <= end:
		for i in range(start, end + 1):
			tsum += p[i][0] * p[i][1]
	print(tsum)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	D = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = []
	f1 = 0
	for i in range(n):
		C.append([A[i], D[i]])
		f1 += D[i]
	C.sort()
	if f1 != n:
		j = len(C) - 1
		l = 0
		for i in range(k):
			f = f1 - B[i]
			if (i + 1) % 2 == 0:
				while f > 0:
					if f - C[j][1] >= 0:
						f -= C[j][1]
						j -= 1
					else:
						w = C[j][1]
						C[j][1] -= f
						f -= w
			else:
				while f > 0:
					if f - C[l][1] >= 0:
						f -= C[l][1]
						l += 1
					else:
						w = C[l][1]
						C[l][1] -= f
						f -= w
			f1 = B[i]
		sum = 0
		if k % 2 == 0:
			while l <= j and f1 >= 0:
				if f1 - C[l][1] > 0:
					sum += C[l][0] * C[l][1]
					f1 -= C[l][1]
					l += 1
				else:
					sum += C[l][0] * f1
					f1 -= C[l][1]
			print(sum)
		else:
			while l < j and f1 >= 0:
				if f1 - C[j][1] > 0:
					sum += C[j][0] * C[j][1]
					f1 -= C[j][1]
					j -= 1
				else:
					sum += C[j][0] * f1
					f1 -= C[j][1]
			print(sum)
	else:
		A.sort()
		j = len(A) - 1
		l = 0
		f1 = n
		for i in range(k):
			f = f1 - B[i]
			if (i + 1) % 2 == 1:
				A = A[f:]
			else:
				A = A[:len(A) - f]
			f1 = B[i]
		sum = 0
		for j in range(len(A)):
			sum += A[j]
		print(sum)


t = int(input())
while t:
	t -= 1
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.append([a[i], d[i]])
	c = sorted(c)
	a = []
	d = []
	for i in range(n):
		a.append(c[i][0])
		d.append(c[i][1])
	b = list(map(int, input().split()))
	cardCounts = sum(d)
	start = 0
	for i in range(k):
		temp = b[i]
		b[i] = cardCounts - b[i]
		cardCounts = temp
		if i % 2:
			while n > 0 and b[i] > 0:
				if b[i] < d[n - 1]:
					d[n - 1] -= b[i]
					break
				b[i] -= d[n - 1]
				n -= 1
		else:
			while start < n - 1 and b[i] > 0:
				if b[i] < d[start]:
					d[start] -= b[i]
					break
				b[i] -= d[start]
				start += 1
	ans = 0
	for i in range(start, n):
		ans += d[i] * a[i]
	print(ans)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split(' ', 2)[:2])
	list1 = list(map(int, input().split(' ', n)[:n]))
	list2 = list(map(int, input().split(' ', n)[:n]))
	list3 = list(map(int, input().split(' ', k)[:k]))
	list4 = []
	s = sum(list2)
	for i in range(n):
		temp = [list1[i], list2[i]]
		list4.append(temp)
	qs = 0
	sum1 = 0
	qe = 2 * n - 1
	list4.sort()
	for i in range(n):
		sum1 += list4[i][0] * list4[i][1]
	for i in range(k):
		if i % 2 == 0:
			c = s - list3[i]
			qs += c
			s = list3[i]
		elif i % 2 != 0:
			c = s - list3[i]
			qe -= c
			s = list3[i]
	qe += 1
	qe = 2 * n - qe
	for i in range(n):
		if qs - list4[i][1] > 0:
			qs -= list4[i][1]
			sum1 -= list4[i][0] * list4[i][1]
			continue
		else:
			sum1 -= list4[i][0] * qs
			break
	for i in range(n - 1, 0, -1):
		if qe - list4[i][1] > 0:
			qe -= list4[i][1]
			sum1 -= list4[i][0] * list4[i][1]
			continue
		else:
			sum1 -= list4[i][0] * qe
			break
	print(sum1)


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(y) for y in input().split()]
	d = [int(u) for u in input().split()]
	b = [int(l) for l in input().split()]
	a1 = [0] * 1000000
	c = 0
	for i in range(len(a)):
		a1[a[i]] += d[i]
		c += d[i]
	sum = 0
	ma = max(a)
	mi = min(a)
	for i in range(k):
		l = c - b[i]
		if i % 2 == 0:
			for j in range(mi, ma + 1):
				if a1[j] != 0:
					if a1[j] >= l:
						a1[j] -= l
						l = 0
						break
					else:
						l -= a1[j]
						a1[j] = 0
						mi = j
		else:
			for j in range(ma, mi - 1, -1):
				if a1[j] != 0:
					if a1[j] >= l:
						a1[j] -= l
						l = 0
						break
					else:
						ma = j
						l -= a1[j]
						a1[j] = 0
		c -= c - b[i]
	for i in range(mi, ma + 1):
		if a1[i] != 0:
			sum += i * a1[i]
	print(sum)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	Alist = list(map(int, input().split()))
	Dlist = list(map(int, input().split()))
	Blist = list(map(int, input().split()))
	(Alist, Dlist) = (list(t) for t in zip(*sorted(zip(Alist, Dlist))))
	C = 0
	for j in range(N):
		C += Dlist[j]
	end = C
	for j in range(len(Blist)):
		if j % 2 == 0:
			start = end - Blist[j]
		else:
			end = start + Blist[j]
	start += 1
	j = 0
	A = Dlist[j]
	ans = 0
	while A < start:
		j += 1
		A += Dlist[j]
	if A >= start and A >= end:
		z = end - start + 1
		ans += z * Alist[j]
	elif A >= start and A < end:
		z = A - start + 1
		ans += z * Alist[j]
		while A < end:
			j += 1
			Acopy = A
			A += Dlist[j]
			if A < end:
				ans += Dlist[j] * Alist[j]
			else:
				z = end - Acopy
				ans += Alist[j] * z
	print(ans)


tc = int(input())
for test in range(tc):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	rm = list(map(int, input().split()))
	k = len(rm)
	my_arr = []
	cards = 0
	for i in range(n):
		my_arr += [[d[i], a[i]]]
		cards += d[i]
	my_arr.sort(key=lambda x: x[1])
	for i in range(k):
		to_del = cards - rm[i]
		if i % 2 != 0:
			start = len(my_arr) - 1
			while to_del != 0:
				if my_arr[start][0] > to_del:
					my_arr[start][0] -= to_del
					to_del = 0
				else:
					to_del -= my_arr[start][0]
					del my_arr[start]
					start -= 1
		else:
			start = 0
			while to_del != 0:
				if my_arr[start][0] > to_del:
					my_arr[start][0] -= to_del
					to_del = 0
				else:
					to_del -= my_arr[start][0]
					del my_arr[start]
		cards = rm[i]
	req_sum = 0
	for i in range(len(my_arr)):
		req_sum += my_arr[i][0] * my_arr[i][1]
	print(req_sum)


t = int(input())
a = []
b = []
for i in range(t):
	n = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	total = 0
	for j in range(n[0]):
		total += b[j]
		c.append((a[j], b[j]))
	c.sort()
	k = list(map(int, input().split()))
	for j in range(n[1]):
		x = k[j]
		x = total - x
		total -= x
		if j % 2 == 0:
			while x > 0:
				if x >= c[0][1]:
					x -= c[0][1]
					c.pop(0)
				elif x < c[0][1]:
					c[0] = (c[0][0], c[0][1] - x)
					x = 0
					break
		elif j % 2 == 1:
			while x > 0:
				if x >= c[-1][1]:
					x -= c[-1][1]
					c.pop(-1)
				elif x < c[-1][1]:
					c[-1] = (c[-1][0], c[-1][1] - x)
					x = 0
					break
	x = 0
	for i in c:
		x += i[0] * i[1]
	print(x)


import io
import sys

def test_data():
	return io.StringIO('1\n4 2\n1 2 3 4\n2 2 2 2\n6 3')

def get_input(source):
	with source as lines:
		t = int(next(lines))
		for _ in range(t):
			(n, k) = map(int, next(lines).strip().split(' '))
			a = list(map(int, next(lines).strip().split(' ')[:n]))
			d = list(map(int, next(lines).strip().split(' ')[:n]))
			b = list(map(int, next(lines).strip().split(' ')[:k]))
			yield (n, k, a, d, b)

def calc(n, k, a, d, b):
	fr = 1
	to = sum(d)
	for (i, num) in enumerate(b):
		if i % 2 == 0:
			fr = to - num + 1
		else:
			to = fr + num - 1
	ind = []
	for i in range(n):
		ind.append({'a': a[i], 'd': d[i]})
	ind = sorted(ind, key=lambda i: i['a'])
	cur = 1
	for i in range(n):
		ind[i]['fr'] = cur
		ind[i]['to'] = cur + ind[i]['d'] - 1
		if fr >= ind[i]['fr'] and fr <= ind[i]['to']:
			ind_fr = i
		if to >= ind[i]['fr'] and to <= ind[i]['to']:
			ind_to = i
		cur = ind[i]['to'] + 1
	total = 0
	for i in range(ind_fr, ind_to + 1):
		total += ind[i]['a'] * (min(ind[i]['to'], to) - max(ind[i]['fr'], fr) + 1)
	return total
inp = test_data() if '-test' in sys.argv else sys.stdin
for args in get_input(inp):
	print(calc(*args))


c = int(input())
for _ in range(c):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	a = list(map(int, input().split()))
	d = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = [(a[i], d[i]) for i in range(n)]
	arr.sort()
	a = [arr[i][0] for i in range(n)]
	d = [arr[i][1] for i in range(n)]
	for i in range(k - 1, 0, -1):
		b[i] = b[i - 1] - b[i]
	b[0] = sum(d) - b[0]
	one = 0
	two = 0
	for i in range(k):
		if i % 2:
			one += b[i]
		else:
			two += b[i]
	i = 0
	j = n - 1
	itill = 0
	jtill = 0
	while itill + d[i] <= two:
		itill += d[i]
		i += 1
	while jtill + d[j] <= one:
		jtill += d[j]
		j -= 1
	x = y = 0
	if i == j:
		print(a[i] * (d[i] - one - two + itill + jtill))
	else:
		x = a[i] * (d[i] - (two - itill))
		y = a[j] * (d[j] - (one - jtill))
		t = 0
		i += 1
		j -= 1
		for k in range(i, j + 1):
			t += a[k] * d[k]
		print(x + y + t)


for _ in range(int(input())):
	[n, k] = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	d = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	p = {}
	for i in range(n):
		try:
			p[a[i]] += d[i]
		except:
			p[a[i]] = d[i]
	val = []
	left = sum(d)
	for i in p:
		val.append([i, p[i]])
	val.sort()
	(si, en) = (0, len(val) - 1)
	for i in range(k):
		if en < si:
			break
		dele = left - b[i]
		left -= dele
		if i % 2 == 0:
			while dele:
				if val[si][1] <= dele:
					dele -= val[si][1]
					si += 1
				else:
					val[si][1] -= dele
					dele = 0
		else:
			while dele:
				if val[en][1] <= dele:
					dele -= val[en][1]
					en -= 1
				else:
					val[en][1] -= dele
					dele = 0
	ans = 0
	if si > en:
		print('0')
		continue
	for i in range(si, en + 1):
		ans += int(val[i][0] * val[i][1])
	print(ans)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	(*A,) = map(int, input().split())
	(*D,) = map(int, input().split())
	(*B,) = map(int, input().split())
	P = sorted(zip(A, D))
	A = [a for (a, d) in P]
	D = [d for (a, d) in P]
	left = 0
	right = sum(D) - 1
	for i in range(K):
		if i % 2 == 0:
			left = right - B[i] + 1
		else:
			right = left + B[i] - 1
	cur = 0
	ans = 0
	for i in range(N):
		if left <= cur + D[i] - 1 and cur <= right:
			ans += A[i] * (min(cur + D[i] - 1, right) - max(cur, left) + 1)
		cur += D[i]
	print(ans)


class CardSet(object):

	def __init__(self, cardValue, cardAmount):
		self.cardValue = cardValue
		self.cardAmount = cardAmount
T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	D = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	cardSets = [CardSet(a, d) for (a, d) in zip(A, D)]
	cardSets.sort(key=lambda x: x.cardValue)
	totalCardsLeft = sum(D)
	chefsMove = True
	for (move, b) in enumerate(B):
		cardsToRemove = totalCardsLeft - b
		if chefsMove:
			while cardsToRemove > 0:
				currentCardSet = cardSets[0]
				if currentCardSet.cardAmount <= cardsToRemove:
					cardSets.pop(0)
					cardsToRemove -= currentCardSet.cardAmount
				else:
					cardSets[0].cardAmount -= cardsToRemove
					cardsToRemove = 0
					break
			chefsMove = not chefsMove
			totalCardsLeft = b
		elif not chefsMove:
			while cardsToRemove > 0:
				currentCardSet = cardSets[-1]
				if currentCardSet.cardAmount <= cardsToRemove:
					cardSets.pop(-1)
					cardsToRemove -= currentCardSet.cardAmount
				else:
					cardSets[-1].cardAmount -= cardsToRemove
					cardsToRemove = 0
					break
			chefsMove = not chefsMove
			totalCardsLeft = b
	totalScore = sum([cardSet.cardValue * cardSet.cardAmount for cardSet in cardSets])
	print(totalScore)