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

You are given two integer arrays A and B each of size N. Let us define interaction of arrays A and B to be the sum of A[i] * B[i] for each i from 1 to N.

You want to maximize the value of interaction of the arrays. You are allowed to make at most K (possibly zero) operations of following kind.

In a single operation, you can increase or decrease any of the elements of array A by 1.

Find out the maximum value of interaction of the arrays that you can get.

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

The first line of input contains a single integer T denoting number of test cases.
For each test case:
	
		First line contains two space separated integers N, K.
		Second line contains N space separated integers denoting array A.
		Third line contains N space separated integers denoting array B.
	
------ Output ------ 

For each test case, output a single integer denoting the answer of the problem.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$0 ≤ |A[i]|, |B[i]| ≤ 10^{5}$
$0 ≤ K ≤ 10^{9}$

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

Subtask #1 : (25 points)

$1 ≤ N ≤ 10$
$0 ≤ |A[i]|, |B[i]| ≤ 10$
$0 ≤ K ≤ 10$

Subtask #2 : (35 points)

$1 ≤ N ≤ 1000$
$0 ≤ |A[i]|, |B[i]| ≤ 1000$
$0 ≤ K ≤ 10^{5}$

Subtask #3 : (40 points)

$No additional constraints$

----- Sample Input 1 ------ 
2
2 2
1 2
-2 3
3 5
1 2 -3
-2 3 -5
----- Sample Output 1 ------ 
10
44
----- explanation 1 ------ 
In the first example, 
you can increase value A[2] using two two operations. Now, A would be [1, 4]. The value of interaction will be 1 * -2 + 4 * 3 = -2 + 12 = 10.

Difficulty: MEDIUM
Tags: Greedy algorithms

Constructive algorithms

Ad-hoc
Skill types: Greedy algorithms

Starter code:

Solutions:
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	x = []
	for i in range(n):
		s += a[i] * b[i]
	for i in range(n):
		x.append(abs(b[i]))
	s += max(x) * k
	print(s)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	data = []
	sum_data = sum((x * y for (x, y) in zip(a, b)))
	for i in range(n):
		data.append(sum_data + k * b[i])
		data.append(sum_data - k * b[i])
	print(max(data))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().lstrip().split()))
	b = list(map(int, input().lstrip().split()))
	total = 0
	for i in range(n):
		total += a[i] * b[i]
	maxi = total
	for i in range(n):
		val1 = maxi
		val2 = maxi
		val1 -= a[i] * b[i]
		val1 += (a[i] + k) * b[i]
		val2 -= a[i] * b[i]
		val2 += (a[i] - k) * b[i]
		total = max(total, val1, val2)
	print(total)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l1 = [int(x) for x in input().split()]
	l2 = [int(x) for x in input().split()]
	(a, b) = ([], [])
	ans = []
	mx = 0
	for i in range(n):
		if mx < abs(l2[i]):
			mx = abs(l2[i])
			ans = [l1[i], l2[i], i]
	res = 0
	if ans:
		if ans[0] >= 0 and ans[1] >= 0:
			res = (ans[0] + k) * ans[1]
		elif ans[0] < 0 and ans[1] < 0:
			res = (ans[0] - k) * ans[1]
		elif ans[0] < 0:
			res = (ans[0] + k) * ans[1]
		else:
			res = (ans[0] - k) * ans[1]
	for i in range(n):
		if ans and i == ans[2]:
			continue
		else:
			res += l1[i] * l2[i]
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	M = 0
	ans = 0
	for i in range(n):
		ans += A[i] * B[i]
		if B[i] < 0:
			B[i] *= -1
		if B[i] > M:
			M = B[i]
	ans += k * M
	print(ans)


t = int(input())
for case in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(maxindex, maxint) = max(enumerate(b), key=lambda x: abs(x[1]))
	sum = 0
	for i in range(n):
		sum += a[i] * b[i]
	print(sum + k * abs(maxint))


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	maximum = -10 ** 6
	ans = 0
	for j in range(n):
		ans += a[j] * b[j]
		maximum = max(maximum, abs(b[j]))
	ans += maximum * k
	print(ans)


t = int(input())
for t in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	print(sum((x * y for (x, y) in zip(a, b))) + k * max(map(abs, b)))


for T in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	sum_interaction = sum(list((n1 * n2 for (n1, n2) in zip(A, B))))
	if abs(min(B)) > max(B):
		sum_interaction += -K * min(B)
	else:
		sum_interaction += K * max(B)
	print(sum_interaction)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	A = [int(num) for num in input().split()]
	B = [int(num) for num in input().split()]
	sum = 0
	for j in range(n):
		sum += A[j] * B[j]
	ma = max(map(abs, B))
	sum += k * ma
	print(sum)


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	res = 0
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	B = []
	for j in range(0, n):
		res = res + a[j] * b[j]
		B.append(abs(b[j]))
	res = res + k * abs(b[B.index(max(B))])
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ali = list(map(int, input().split()))
	bli = list(map(int, input().split()))
	ind = -1
	for i in range(n):
		if ind == -1:
			ind = i
		elif abs(bli[ind]) < abs(bli[i]):
			ind = i
	sum = 0
	for i in range(n):
		if i != ind:
			sum += ali[i] * bli[i]
		else:
			sum += ali[i] * bli[i]
			sum += k * abs(bli[i])
	print(sum)


def interaction(a, b):
	sum = 0
	for i in range(len(a)):
		sum += a[i] * b[i]
	return sum
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	l = [abs(x) for x in b]
	if b[l.index(max(l))] > 0:
		a[l.index(max(l))] += k
	elif b[l.index(max(l))] < 0:
		a[l.index(max(l))] -= k
	print(interaction(a, b))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mb = (b[0], 0)
	for i in range(len(b)):
		if abs(b[i]) > abs(mb[0]):
			mb = (b[i], i)
	if mb[0] >= 0:
		a[mb[1]] += k
	else:
		a[mb[1]] -= k
	s = 0
	for i in range(n):
		s += a[i] * b[i]
	print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	(ravan, aman) = (0, 0)
	for j in range(n):
		if abs(y[j]) > ravan:
			ravan = abs(y[j])
		aman += x[j] * y[j]
	print(aman + k * ravan)


t = int(input())
for i in range(t):
	(length, operations) = map(int, input().split())
	arr = []
	total = 0
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	for j in range(length):
		arr.append([arr1[j], arr2[j]])
		total += arr1[j] * arr2[j]
	arr.sort(key=lambda x: x[1], reverse=True)
	if arr[0][1] > arr[-1][1] * -1:
		total += operations * arr[0][1]
	else:
		total += -operations * arr[-1][1]
	print(total)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	orig = 0
	for i in range(n):
		orig += A[i] * B[i]
	a = max(B)
	b = min(B)
	c = max(abs(a), abs(b))
	print(orig + k * c)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	s = 0
	for j in range(n):
		s = s + x[j] * y[j]
	a = s + max(y) * k
	b = s + min(y) * -k
	print(max(a, b))


T = int(input())
for j in range(T):
	in1 = [int(i) for i in input().split()]
	(N, K) = (in1[0], in1[1])
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	P = K * max([abs(l) for l in [max(B), min(B)]])
	for i in range(0, N):
		P += A[i] * B[i]
	print(P)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	for i in range(n):
		if a[i] <= 0 and b[i] <= 0:
			(a[i], b[i]) = (-a[i], -b[i])
	x = 0
	for i in range(n):
		if abs(b[i]) > abs(b[x]):
			x = i
	if b[x] < 0:
		a[x] -= k
	else:
		a[x] += k
	ans = 0
	for i in range(n):
		ans += a[i] * b[i]
	print(ans)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	a = input().split()
	b = input().split()
	a = [int(i) for i in a]
	b = [int(i) for i in b]
	sumn = 0
	temp = 0
	for i in range(len(a)):
		sumn += a[i] * b[i]
	temp2 = sumn
	for i in range(len(b)):
		if a[i] >= 0 and b[i] >= 0 or (a[i] < 0 and b[i] < 0):
			temp = sumn + k * abs(b[i])
		else:
			temp1 = sumn - k * b[i]
			temp3 = sumn + k * b[i]
			temp = max(temp1, temp3)
		if temp > temp2:
			temp2 = temp
	print(temp2)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	min_el = min(B)
	max_el = max(B)
	ind = 0
	if abs(min_el) < max_el:
		ind = B.index(max_el)
		A[ind] = A[ind] + K
	elif min_el == max_el:
		if min_el >= 0:
			ind = A.index(max(A))
			A[ind] = A[ind] + K
		else:
			ind = A.index(min(A))
			A[ind] = A[ind] - K
	else:
		ind = B.index(min_el)
		A[ind] = A[ind] - K
	res = 0
	for (a, b) in zip(A, B):
		res += a * b
	print(res)


t = int(input())
for jhdfj in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s += a[i] * b[i]
	s += k * max(abs(max(b)), abs(min(b)))
	print(s)


from sys import flags
for _ in range(int(input())):
	(n, k) = [int(a) for a in input().split()]
	arr = [int(a) for a in input().split()]
	brr = [int(a) for a in input().split()]
	val = -float('inf')
	for l in brr:
		val = max(val, abs(l))
		val2 = 0
	for l in range(n):
		val2 = val2 + arr[l] * brr[l]
	print(val2 + val * k)


for _ in range(int(input().strip())):
	(n, k) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	ans = 0
	ans += sum((x * y for (x, y) in zip(a, b)))
	ans += k * max(map(abs, b))
	print(ans)


def solution(a, b, k):
	s = sum((x * y for (x, y) in zip(a, b)))
	maxi = s + 0
	for i in range(len(b)):
		if s + k * b[i] > maxi:
			maxi = s + k * b[i]
		if s - k * b[i] > maxi:
			maxi = s - k * b[i]
	return maxi
T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(solution(a, b, K))


T = int(input())
while T > 0:
	(N, K) = map(int, input().split())
	A = [int(n) for n in input().split()]
	B = [int(n) for n in input().split()]
	result = 0
	inter = 0
	for i in range(N):
		result += A[i] * B[i]
	inter = result
	for i in range(N):
		if A[i] >= 0 and B[i] >= 0 or (A[i] < 0 and B[i] < 0):
			temp = result + K * abs(B[i])
		else:
			temp1 = result - K * abs(B[i])
			temp2 = result + K * abs(B[i])
			temp = max(temp1, temp2)
		inter = max(inter, temp)
	print(inter)
	T = T - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s += a[i] * b[i]
	m = max([abs(i) for i in b])
	print(s + k * m)


for i in range(int(input())):
	s = input().split()
	s = [int(j) for j in s]
	l1 = input().split()
	l2 = input().split()
	l1 = [int(j) for j in l1]
	l2 = [int(j) for j in l2]
	mx = abs(l2[0])
	k = 0
	for j in range(len(l2)):
		if abs(l2[j]) > mx:
			mx = abs(l2[j])
			k = j
	if l2[k] > 0:
		l1[k] = l1[k] + s[1]
	else:
		l1[k] = l1[k] - s[1]
	sum = 0
	for j in range(s[0]):
		sum = sum + l1[j] * l2[j]
	print(sum)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	min_el = min(B)
	max_el = max(B)
	ind = 0
	if abs(min_el) < max_el:
		ind = B.index(max_el)
		A[ind] = A[ind] + K
	elif min_el == max_el:
		if min_el >= 0:
			ind = A.index(max(A))
			A[ind] = A[ind] + K
		else:
			ind = A.index(min(A))
			A[ind] = A[ind] - K
	else:
		ind = B.index(min_el)
		A[ind] = A[ind] - K
	res = 0
	for (a, b) in zip(A, B):
		res += a * b
	print(res)


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sum1 = sum(list((n1 * n2 for (n1, n2) in zip(a, b))))
	max_b = max(b)
	min_b = min(b)
	if -min_b > max_b:
		sum1 = sum1 - K * min_b
	else:
		sum1 = sum1 + K * max_b
	print(sum1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans = max(ans, abs(arr[i]))
	ans = ans * k
	ans += sum((a * b for (a, b) in zip(l, arr)))
	print(ans)


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mx = -99999999
	for i in b:
		mx = max(mx, abs(i))
	ii = 0
	for i in range(n):
		ii = ii + a[i] * b[i]
	ii = ii + mx * k
	print(ii)


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(mx, mn) = (max(b), min(b))
	val = mx if abs(mx) > abs(mn) else mn
	idx = b.index(val)
	if val > 0:
		a[idx] += k
	else:
		a[idx] -= k
	s = 0
	for i in range(n):
		s = s + a[i] * b[i]
	print(s)


import sys
from random import randint

def read_ints(inp=sys.stdin):
	return list(map(int, next(inp).strip().split()))

def brute(seq):
	return 0

def testseq():
	for n in range(1, 100):
		seq = [randint(n) for _ in range(n)]
		ref = brute(seq)
		r1 = sol1(seq)
		if ref != r1:
			print(n)
			print(seq)
			print(ref)
			print(r1)
			assert False

def sol1(A, B, k):
	(_, idx) = max(((abs(x), i) for (i, x) in enumerate(B)))
	if B[idx] > 0:
		A[idx] += k
	else:
		A[idx] -= k
	return sum((a * b for (a, b) in zip(A, B)))
if 0:
	inp = iter('2\n2 2\n1 2\n-2 3\n3 5\n1 2 -3\n-2 3 -5\n'.split('\n'))
else:
	inp = sys.stdin
(T,) = read_ints(inp)
for _ in range(T):
	(N, K) = read_ints(inp)
	A = read_ints(inp)
	B = read_ints(inp)
	print(sol1(A, B, K))


Test = int(input())
while Test != 0:
	maxi = 0
	(N, K) = map(int, input().split())
	A = []
	B = []
	A = input().split()
	B = input().split()
	for j in range(N):
		A[j] = int(A[j])
		B[j] = int(B[j])
		if maxi < abs(B[j]):
			maxi = abs(B[j])
			loc = j
	prod = 0
	for j in range(len(B)):
		prod = prod + A[j] * B[j]
	prod = prod + maxi * K
	print(prod)
	Test = Test - 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		ans += a[i] * b[i]
	d = ans
	for i in range(n):
		d = max(d, ans + k * b[i])
		d = max(d, ans + -1 * k * b[i])
	print(d)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	interaction = 0
	mx = -float('INF')
	for item in b:
		mx = max(mx, abs(item))
	for i in range(n):
		interaction += a[i] * b[i]
	interaction += mx * k
	print(interaction)


from math import *
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ind = -1
	for i in range(n):
		if ind == -1:
			ind = i
		elif abs(b[ind]) < abs(b[i]):
			ind = i
	sm = 0
	for i in range(n):
		if i != ind:
			sm += a[i] * b[i]
		else:
			sm += a[i] * b[i]
			sm += k * abs(b[i])
	print(sm)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	mx = -float('INF')
	for item in brr:
		mx = max(mx, abs(item))
	ii = 0
	for i in range(n):
		ii = ii + arr[i] * brr[i]
	ii = ii + mx * k
	print(ii)


for cas in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		a[i] = a[i] * b[i]
		b[i] = abs(b[i])
	s = sum(a)
	p = max(b)
	print(s + k * abs(p))


for t in range(int(input())):
	ans = 0
	(n, k) = map(int, input().split())
	arrA = list(map(int, input().split()))
	arrB = list(map(int, input().split()))
	for i in range(len(arrA)):
		ans += arrA[i] * arrB[i]
		if arrB[i] < 0:
			arrB[i] *= -1
	print(ans + k * max(arrB))


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	for i in range(0, n):
		c += a[i] * b[i]
	mx = b[0]
	for i in range(1, n):
		mx = max(mx, abs(b[i]))
	c += k * mx
	print(c)
	t -= 1


t = int(input())
for _ in range(0, t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sum = 0
	for i in range(0, n):
		sum += a[i] * b[i]
	max = 0
	ii = 0
	for i in range(0, n):
		if max < abs(b[i]):
			max = abs(b[i])
			ii = i
	if b[ii] < 0:
		sum += -k * b[ii]
	else:
		sum += k * b[ii]
	print(sum)


t = int(input())
for i in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	a = input().split(' ')
	b = input().split(' ')
	maxi = 0
	ind = 0
	for z in range(n):
		val = int(b[z])
		if abs(val) > maxi:
			maxi = abs(val)
			ind = z
			s = int(val / abs(val))
	a[ind] = int(a[ind]) + s * k
	sumo = 0
	for z in range(n):
		sumo += int(a[z]) * int(b[z])
	print(sumo)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	mul = [a[x] * b[x] for x in range(n)]
	absb = [abs(x) for x in b]
	mx = max(absb)
	index = absb.index(mx)
	su = sum(mul)
	print(su + (a[index] - k) * b[index] - a[index] * b[index]) if b[index] < 0 else print(su + (a[index] + k) * b[index] - a[index] * b[index])


n = int(input())
for i in range(n):
	p = input()
	(n, k) = p.split()
	(n, k) = (int(n), int(k))
	a = input()
	b = input()
	la = [int(s) for s in a.strip().split(' ')]
	lb = [int(s) for s in b.strip().split(' ')]
	maxb = 0
	mai = -1
	ms = 1
	for i in range(n):
		temp = abs(lb[i])
		if temp > maxb:
			maxb = temp
			mai = i
	if la[mai] * lb[mai] >= 0:
		if la[mai] > 0:
			la[mai] = la[mai] + k
		else:
			la[mai] = la[mai] - k
	elif la[mai] > 0:
		la[mai] = la[mai] - k
	else:
		la[mai] = la[mai] + k
	multia = [la[i] * lb[i] for i in range(n)]
	res = sum(multia)
	print(res)


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split(' '))
	list_A = list(map(int, input().split(' ')))
	list_B = list(map(int, input().split(' ')))
	mx = 0
	sumall = 0
	for i in range(n):
		c = list_A[i] * list_B[i]
		sumall += c
		if list_B[i] > 0:
			d = list_A[i] + k
		else:
			d = list_A[i] - k
		if list_B[i] * d - c > mx:
			mx = list_B[i] * d - c
	print(sumall + mx)


for _ in range(int(input())):
	arr = input().split()
	(n, k) = (int(arr[0]), int(arr[1]))
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	for i in range(n):
		if b[i] < 0:
			b[i] *= -1
			a[i] *= -1
	m = b.index(max(b))
	a[m] += k
	print(sum([a[i] * b[i] for i in range(n)]))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	c = list(map(lambda x, y: x * y, a, b))
	m = max(list(map(lambda x: abs(x), b)))
	csum = sum(c)
	print(csum + k * m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(a, b) = (list(map(int, input().split())), list(map(int, input().split())))
	res = 0
	for i in range(n):
		res += a[i] * b[i]
	m = 0
	for i in range(n):
		if abs(b[i]) > m:
			m = abs(b[i])
			pos = i
	res = max(res, res - k * b[pos], res + k * b[pos])
	print(res)


t = int(input())
for i in range(t):
	a = []
	b = []
	(n, k) = map(int, input().split())
	a = list(map(int, input().strip().split()))[:n]
	b = list(map(int, input().strip().split()))[:n]
	max = abs(b[0])
	ind = 0
	sum = 0
	for j in range(n):
		if abs(b[j]) > max:
			max = abs(b[j])
			ind = j
	for j in range(n):
		sum = sum + a[j] * b[j]
	print(sum + k * abs(b[ind]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = [int(i) for i in input().split()]
	B = [int(i) for i in input().split()]
	maxi = 0
	s = 0
	for i in range(n):
		if abs(B[i]) > maxi:
			maxi = abs(B[i])
		s += A[i] * B[i]
	print(s + maxi * k)


for _ in range(int(input())):
	maxx = -100005
	summ = 0
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	for i in range(n):
		if maxx < abs(brr[i]):
			maxx = abs(brr[i])
			index = i
	for i in range(n):
		if i == index:
			if brr[i] < 0:
				arr[i] -= k
			else:
				arr[i] += k
		summ += arr[i] * brr[i]
	print(summ)


for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	k = temp[1]
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	x = abs(b[0])
	for i in range(n):
		ans += a[i] * b[i]
		if abs(b[i]) > x:
			x = abs(b[i])
	ans += x * k
	print(ans)


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		y = -10 ** 100
		for i in range(n):
			y = max(y, abs(b[i]))
		ans = 0
		for i in range(n):
			ans += a[i] * b[i]
		ans += y * k
		print(ans)
except Exception:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = [int(i) for i in input().split(' ')]
	b = [int(i) for i in input().split(' ')]
	c = 0
	final = 0
	for i in range(n):
		c += a[i] * b[i]
		final += a[i] * b[i]
	for i in range(n):
		p = 1 if b[i] >= 0 else -1
		temp = c + p * k * b[i]
		if temp > final:
			final = temp
	print(final)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(((bi, ai) for (ai, bi) in zip(map(int, input().split()), map(int, input().split()))))
	v = sum((bi * ai for (bi, ai) in a))
	if a[-1][0] > 0 and a[-1][0] >= -a[0][0]:
		v += k * a[-1][0]
	elif a[0][0] < 0:
		v += k * -a[0][0]
	print(v)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	f = max(b)
	r = min(b)
	sum = 0
	for i in range(n):
		sum += a[i] * b[i]
		b[i] = abs(b[i])
	sum += k * max(b)
	print(sum)


t = int(input())
for i in range(t):
	s = list(map(int, input().split()))
	n = s[0]
	k = s[1]
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = 0
	for i in range(n):
		c += a[i] * b[i]
	mi = min(b)
	ma = max(b)
	if ma < -mi:
		ma = -mi
	c += k * ma
	print(c)


def soln(n, k, a, b):
	res = 0
	orig = 0
	maxm = 0
	for i in range(n):
		res += a[i] * b[i]
	res += k * max(abs(max(b)), abs(min(b)))
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(soln(n, k, a, b))


t = int(input())
for test in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	s = sum((x * y for (x, y) in zip(a, b)))
	mx = 0
	pair = 0
	for i in range(n):
		if abs(b[i]) > abs(mx):
			mx = b[i]
			pair = a[i]
		elif abs(b[i]) == abs(mx) and abs(a[i]) > abs(pair):
			pair = a[i]
	s -= mx * pair
	if mx < 0:
		(mx, pair) = (-mx, -pair)
	if (mx > 0) != (pair > 0):
		if -k >= pair:
			k += pair
			pair = 0
		else:
			pair += k
			k = 0
	pair += k
	s += mx * pair
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	Ai = list(map(int, input().split()))
	Bi = list(map(int, input().split()))
	maximum = 0
	index = 0
	for i in range(n):
		if abs(Bi[i]) > maximum:
			maximum = abs(Bi[i])
			index = i
	if Bi[index] < 0:
		Ai[index] -= k
	else:
		Ai[index] += k
	result = 0
	for i in range(n):
		result += Ai[i] * Bi[i]
	print(result)


for i in range(int(input())):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	total = 0
	for j in range(N):
		total += A[j] * B[j]
	total += K * max(abs(max(B)), abs(min(B)))
	print(total)


from math import fabs

def getkey(a):
	return int(fabs(a[1]))
t = int(input())
for k in range(t):
	(n, k) = map(int, input().split(' '))
	a = [int(i) for i in input().split(' ')]
	b = [int(i) for i in input().split(' ')]
	g = []
	for i in range(n):
		g.append([a[i], b[i]])
	g.sort(key=getkey, reverse=True)
	if g[0][1] >= 0:
		g[0][0] += k
	else:
		g[0][0] -= k
	ss = 0
	for i in range(n):
		ss += g[i][0] * g[i][1]
	print(ss)


def main():
	t = int(input())
	while t:
		t -= 1
		(n, k) = [int(i) for i in input().split()]
		a = [int(i) for i in input().split()]
		b = [int(i) for i in input().split()]
		ssum = sum([n1 * n2 for (n1, n2) in zip(a, b)])
		mmax = max(b)
		mmin = min(b)
		if abs(mmin) > mmax:
			ssum += k * abs(mmin)
		else:
			ssum += k * mmax
		print(ssum)
main()


q = int(input())
for i in range(0, q):
	temp = list(map(int, input().split(' ', 2)[:2]))
	n = temp[0]
	k = temp[1]
	listA = list(map(int, input().split(' ', n)[:n]))
	listB = list(map(int, input().split(' ', n)[:n]))
	sum1 = 0
	for j in range(0, n):
		sum1 = sum1 + listA[j] * listB[j]
	max1 = sum1
	for j in range(0, n):
		sum2 = sum1
		sum2 -= listA[j] * listB[j]
		if listA[j] < 0 and listB[j] < 0:
			listA[j] -= k
		elif listA[j] < 0 and listB[j] >= 0:
			listA[j] += k
		elif listA[j] >= 0 and listB[j] < 0:
			listA[j] -= k
		else:
			listA[j] += k
		sum2 += listA[j] * listB[j]
		if max1 < sum2:
			max1 = sum2
	print(max1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	x = 0
	m = 0
	sum = 0
	for i in range(n):
		r = a[i] * b[i]
		sum = sum + r
		p = (a[i] + 1) * b[i]
		q = (a[i] - 1) * b[i]
		y = max(p, q)
		y = y - r
		if y > m:
			m = y
	sum = sum + k * m
	print(sum)


for _ in range(int(input())):
	(N, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	print(sum([arr[i] * brr[i] for i in range(len(arr))]) + max(map(abs, brr)) * k)


T = int(input())
while T:
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	ans = 0
	for i in range(len(A)):
		ans += A[i] * B[i]
		B[i] = abs(B[i])
	ans += K * max(B)
	print(ans)
	T -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(mb, mbi) = (0, 0)
	for i in range(n):
		if b[i] < 0:
			if mb < -1 * b[i]:
				mb = -1 * b[i]
				mbi = i
		elif mb < b[i]:
			mb = b[i]
			mbi = i
	if b[mbi] < 0:
		a[mbi] -= k
	else:
		a[mbi] += k
	ans = 0
	for i in range(n):
		ans += a[i] * b[i]
	print(ans)


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


def temp(n, k):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	max_i = 0
	m1 = abs(b[0])
	j = 0
	for i in range(n):
		if m1 < abs(b[i]):
			m1 = abs(b[i])
			j = i
		max_i += a[i] * b[i]
	max_i = max_i + k * abs(b[j])
	return max_i
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(temp(n, k))