Read problems statements in [Mandarin Chinese], [Russian], and [Bengali] as well.

After solving programming problems for years, Chef has become lazy and decided to get a better physique by doing some weight lifting exercises.

On any regular day, Chef does $N$ exercises at times $A_{1}, A_{2}, \ldots, A_{N}$ (in minutes, all distinct) and each exercise provides a tension of $B_{1}, B_{2}, \ldots, B_{N}$ units. In the period between two consecutive exercises, his muscles relax $R$ units of tension per minute.

More formally, Chef's tension is described by a number $x$. Before any workouts, $x=0$. When he does a workout at time $A_{i}$, the tension $x$ instantly increases by $B_{i}$. Between workouts, the number $x$ decreases by $R$ units per minute, maximized with $0$.

Considering the time of exercise and hence tension to be negligible, find the maximum tension he will be feeling in his muscles during the entire period of his workout.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains $3$ lines of input.
The first line will contain $2$ space-separated integers $N, R$, number of timestamps at which Chef performs his exercise, and units of tension relaxed per minute.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
The third line contains $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$.  

------ Output: ------
For each testcase, output in a single line the maximum amount of tension Chef will have in his muscles.

------ Constraints  ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 5\cdot 10^{4}$
$1 ≤ R, B_{i} ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
$A_{i - 1} < A_{i}$, for all $2≤ i≤ N$

----- Sample Input 1 ------ 
3

1 2

10

10

2 2

10 11

10 10

3 1

1 2 3

1 2 3
----- Sample Output 1 ------ 
10

18

4
----- explanation 1 ------ 
Test Case 1: Since there is only $1$ exercise, the maximum tension is equal to the tension provided by that exercise, i.e, $10$ units. 

Test Case 2: At time $t = 10$, Chef has $10$ units of tension. 

From $t = 10$ to $t = 11$, his muscles releases $2$ unit of tension and at $t = 11$, he further gains $10$ units of tension to have total of $10 - 2 + 10 = 18$ units of tension.

So the maximum tension Chef feels in his muscles is $18$ units.

Test Case 3: At time $t = 1$, Chef has $1$ unit of tension. 

From $t = 1$ to $t = 2$, his muscles releases $1$ unit of tension and at $t = 2$, he further gains $2$ units of tension to have total of $1 - 1 + 2 = 2$ units of tension.

From $t = 2$ to $t = 3$, his muscles releases $1$ unit of tension and at $t = 3$, he further gains $3$ units of tension to have total of $2 - 1 + 3 = 4$ units of tension. 

So the maximum tension Chef feels in his muscles is $4$ units.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Implementation

Complete search

Mathematics

Ad-hoc
Skill types: Complete search

Starter code:

Solutions:
for i in range(int(input())):
	(n, r) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	maxt = b[0]
	t = b[0]
	x = b[0]
	for j in range(1, n):
		prev = a[j - 1]
		curr = a[j]
		x = max(b[j], x + b[j] - (curr - prev) * r)
		if x > maxt:
			maxt = x
	print(maxt)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = b[0]
	c = b[0]
	for i in range(1, n):
		gap = a[i] - a[i - 1]
		dec = gap * r
		if dec > c:
			c = 0
		else:
			c -= dec
		c += b[i]
		if c > m:
			m = c
	print(m)


def main():
	T = int(input())
	for counter in range(T):
		(n, r) = map(int, input().split())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		bestsum = 0
		currsum = 0
		for i in range(n):
			currsum = max(0, currsum + b[i])
			bestsum = max(currsum, bestsum)
			if i < n - 1:
				currsum = max(0, currsum - (a[i + 1] - a[i]) * r)
				bestsum = max(currsum, bestsum)
		print(bestsum)
main()


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


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

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
t = int(input())
for _ in range(t):
	(n, r) = integer_list()
	a_lst = integer_list()
	b_lst = integer_list()
	tension = b_lst[0]
	time = a_lst[0]
	ans = b_lst[0]
	for i in range(1, n):
		t = a_lst[i] - time
		tension = max(0, tension - r * t)
		time = a_lst[i]
		tension += b_lst[i]
		ans = max(ans, tension)
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = temp = b[0]
	for i in range(1, n):
		temp -= (a[i] - a[i - 1]) * r
		if temp < 0:
			temp = 0
		temp += b[i]
		if temp > ans:
			ans = temp
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	time = list(map(int, input().split()))
	Tension = list(map(int, input().split()))
	ans = Tension[0]
	x = Tension[0]
	for i in range(1, n):
		time_gap = time[i] - time[i - 1]
		x += Tension[i] - min(time_gap * r, x)
		ans = max(ans, x)
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	t = list(map(int, input().split()))
	T = list(map(int, input().split()))
	ans = T[0]
	x = T[0]
	for i in range(1, n):
		time_gap = t[i] - t[i - 1]
		x += T[i] - min(time_gap * r, x)
		ans = max(ans, x)
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	if n == 1:
		print(list2[0])
		continue
	summ = list2[0]
	maxx = list2[0]
	for i in range(1, n):
		if r * (list1[i] - list1[i - 1]) >= summ:
			summ = list2[i]
		else:
			summ += list2[i] - r * (list1[i] - list1[i - 1])
		if summ > maxx:
			maxx = summ
	print(maxx)


t = int(input())
while t != 0:
	t -= 1
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	tension = 0
	ans = 0
	for i in range(n):
		tension += b[i]
		ans = max(ans, tension)
		if i != n - 1:
			tension -= r * (a[i + 1] - a[i])
		if tension < 0:
			tension = 0
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	k = []
	su = 0
	for i in range(len(l1)):
		if i != len(l1) - 1:
			su += l1[i]
			c = b * (l[i + 1] - l[i])
			k.append(su)
			su -= c
			if su < 0:
				su = 0
		else:
			su += l1[i]
			k.append(su)
	print(max(k))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1.append(l1[-1])
	pump = 0
	ans = 0
	for i in range(len(l1)):
		try:
			pump += l2[i]
		except IndexError:
			pass
		if ans < pump:
			ans = pump
		try:
			diff = l1[i + 1] - l1[i]
			diff = diff * k
			pump = pump - diff
			if pump < 0:
				pump = 0
		except IndexError:
			pass
		if ans < pump:
			ans = pump
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(tot, m) = (0, 0)
	for i in range(n):
		tot += b[i]
		if tot > m:
			m = tot
		if i < n - 1:
			tot -= (a[i + 1] - a[i]) * r
		if tot < 0:
			tot = 0
	print(m)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(t, m) = (0, 0)
	for x in range(n):
		t += b[x]
		if t > m:
			m = t
		if x < n - 1:
			t -= (a[x + 1] - a[x]) * r
		if t < 0:
			t = 0
	print(m)


for i in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = 0
	res = 0
	for i in range(0, n):
		x += b[i]
		res = max(x, res)
		if i != n - 1:
			x -= (a[i + 1] - a[i]) * r
		if x < 0:
			x = 0
	print(res)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, r) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = b[0]
	r_ans = ans
	for i in range(1, n):
		ext = r * (a[i] - a[i - 1])
		ans -= ext
		ans = max(ans, 0)
		ans += b[i]
		r_ans = max(r_ans, ans)
	print(r_ans)


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


for i in range(int(input())):
	(n, r) = map(int, input().split())
	li1 = list(map(int, input().split()))
	li2 = list(map(int, input().split()))
	rel = 0
	ten = li2[0]
	ma = li2[0]
	if n > 1:
		for j in range(1, n):
			ten -= (li1[j] - li1[j - 1]) * r
			if ten < 0:
				ten = 0
			ten += li2[j]
			if ten > ma:
				ma = ten
	print(ma)


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


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	(res, ex) = (0, 0)
	for i in range(n):
		ex += B[i]
		res = max(res, ex)
		if i != n - 1:
			ex -= (A[i + 1] - A[i]) * r
			ex = max(0, ex)
	print(res)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	li = list(map(int, input().split()))
	bi = list(map(int, input().split()))
	tension = 0
	result = 0
	for i in range(n):
		tension += bi[i]
		result = max(tension, result)
		if i + 1 < n:
			k = li[i + 1] - li[i]
			k = k * r
			if tension >= k:
				tension -= k
			else:
				tension = 0
		else:
			pass
	print(result)


for t in range(int(input())):
	(n, r) = map(int, input().split())
	time = [int(x) for x in input().split()]
	tension = [int(x) for x in input().split()]
	max = 0
	temp_t = 0
	i = 0
	while i < n:
		if n == 1:
			max = tension[0]
			break
		elif i > 0:
			if temp_t >= (time[i] - time[i - 1]) * r:
				temp_t -= (time[i] - time[i - 1]) * r
			else:
				temp_t = 0
		temp_t += tension[i]
		if temp_t > max:
			max = temp_t
		i = i + 1
	print(max)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ma = -999
	res = 0
	for i in range(n - 1):
		res += b[i]
		ma = max(ma, res)
		res -= abs(a[i + 1] - a[i]) * r
		if res < 0:
			res = 0
	ma = max(ma, res + b[n - 1])
	print(ma)


import math
for _ in range(int(input())):
	(n, r) = map(int, input().split())
	tli = list(map(int, input().split()))
	fli = list(map(int, input().split()))
	x = fli[0]
	maxa = fli[0]
	for i in range(1, n):
		maxa = maxa - (tli[i] - tli[i - 1]) * r
		if maxa < 0:
			maxa = 0
		maxa = maxa + fli[i]
		x = max(x, maxa)
	print(x)


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


t = int(input())
for i in range(t):
	(n, r) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	ma = -999
	res = 0
	for i in range(n - 1):
		res += b[i]
		ma = max(ma, res)
		res -= abs(a[i + 1] - a[i]) * r
		if res < 0:
			res = 0
	ma = max(ma, res + b[n - 1])
	print(ma)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if len(a) == 1:
		print(b[0])
		continue
	ans = b[0]
	m = 0
	for i in range(1, n):
		ans -= r * (a[i] - a[i - 1])
		if ans < 0:
			ans = 0
		ans += b[i]
		if ans > m:
			m = ans
	print(m)


for t in range(int(input())):
	(n, t) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = 0
	m = 0
	for i in range(n):
		if i != 0:
			x = max(0, x - t * (a[i] - a[i - 1]))
		x += b[i]
		m = max(m, x)
	print(m)


t = int(input())
for tc in range(t):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	tension = []
	x = b[0]
	tension.append(x)
	for i in range(1, n):
		x = max(0, x - r * (a[i] - a[i - 1]))
		x += b[i]
		tension.append(x)
	print(max(tension))


t = int(input())
for _ in range(t):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = []
	x = 0
	for i in range(len(a)):
		if i != len(a) - 1:
			x += b[i]
			ans.append(x)
			d = abs(a[i + 1] - a[i])
			d = d * r
			x -= d
			if x < 0:
				x = 0
		else:
			x += b[i]
			ans.append(x)
	print(max(ans))


t = int(input())
for i in range(t):
	c = 0
	cc = []
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(0, len(a)):
		if i != len(a) - 1:
			c += b[i]
			cc.append(c)
			di = abs(a[i] - a[i + 1])
			di = di * y
			c -= di
			if c < 0:
				c = 0
		else:
			c += b[i]
			cc.append(c)
	print(max(cc))


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


for num in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	res = b[0]
	flag = res
	for i in range(1, n):
		flag = flag - r * (a[i] - a[i - 1])
		flag = max(flag, 0)
		flag = flag + b[i]
		res = max(flag, res)
	print(res)


t = int(input())
for _ in range(t):
	(n, r) = input().split()
	n = int(n)
	r = int(r)
	A = list((int(x) for x in input().split()))
	B = list((int(x) for x in input().split()))
	x = 0
	t_max = 0
	for i in range(n):
		x += B[i]
		if x > t_max:
			t_max = x
		if i <= n - 2:
			x = max(0, x - r * (A[i + 1] - A[i]))
	print(t_max)


for i in range(int(input())):
	(n, r) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	s = B[0]
	m = B[0]
	for j in range(1, n):
		m = max(s, m)
		s = max(0, s - abs(A[j] - A[j - 1]) * r)
		s += B[j]
	print(max(m, s))


t = int(input())
for i in range(t):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if n == 1:
		print(b[0])
	else:
		te = b[0]
		max = -1
		for j in range(1, n):
			value = a[j] - a[j - 1]
			lost = value * r
			te -= lost
			if te < 0:
				te = 0
			te += b[j]
			if max < te:
				max = te
		print(max)


def build(n, r, time, tension):
	if n == 1:
		return tension[0]
	t = tension[0]
	max_tension = -1
	for i in range(1, n):
		value = time[i] - time[i - 1]
		lost = value * r
		t -= lost
		if t < 0:
			t = 0
		t += tension[i]
		if t > max_tension:
			max_tension = t
	return max_tension
t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	(n, r) = (l[0], l[1])
	time = list(map(int, input().split()))
	tension = list(map(int, input().split()))
	print(build(n, r, time, tension))


t = int(input())
for _ in range(t):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = b[0]
	tension = []
	tension.append(x)
	for i in range(1, n):
		diff = a[i] - a[i - 1]
		x = x - diff * r
		if x < 0:
			x = 0
		x += b[i]
		tension.append(x)
	print(max(tension))


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = b[0]
	t = b[0]
	for i in range(1, len(a)):
		d = a[i] - a[i - 1]
		x = x - d * r
		if x < 0:
			x = 0
		x += b[i]
		if x > t:
			t = x
	print(t)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = b[0]
	max_tension = b[0]
	for i in range(1, len(a)):
		diff = a[i] - a[i - 1]
		x = x - diff * r
		if x < 0:
			x = 0
		x += b[i]
		if x > max_tension:
			max_tension = x
	print(max_tension)


for t in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	max_t = b[0]
	updated_t = b[0]
	for i in range(1, len(b)):
		new_r = (a[i] - a[i - 1]) * r
		if updated_t - new_r < 0:
			updated_t = 0 + b[i]
		else:
			updated_t = updated_t + b[i] - new_r
		if updated_t > max_t:
			max_t = updated_t
	print(max_t)


def solve():
	(n, r) = list(map(int, input().split()))
	alst = list(map(int, input().split()))
	blst = list(map(int, input().split()))
	tension = blst[0]
	maxtension = tension
	t = alst[0]
	for (a, b) in zip(alst[1:], blst[1:]):
		tension = max(0, tension - (a - t) * r)
		t = a
		tension += b
		maxtension = max(tension, maxtension)
	return maxtension
t = int(input())
for _ in range(t):
	ans = solve()
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	exer = [int(i) for i in input().split()]
	tension = [int(i) for i in input().split()]
	max_ans = 0
	temp = 0
	for i in range(n - 1):
		temp += tension[i]
		if temp > max_ans:
			max_ans = temp
		temp -= (exer[i + 1] - exer[i]) * r
		if temp < 0:
			temp = 0
	temp += tension[-1]
	if temp > max_ans:
		max_ans = temp
	print(max_ans)


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


for i in range(int(input())):
	(N, R) = map(int, input().split())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	s = m[0]
	o = m[0]
	for i in range(1, len(l)):
		o = o - R * (l[i] - l[i - 1])
		if o <= 0:
			o = 0
		o += m[i]
		if o > s:
			s = o
	print(s)


for i in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(max_t, t) = (0, 0)
	for j in range(len(a)):
		if t >= max_t:
			max_t = t
		if j == 0:
			t = b[j]
			max_t = b[j]
		elif t - r * (a[j] - a[j - 1]) <= 0 and t != 0:
			t = b[j]
			if t >= max_t:
				max_t = t
		elif t - r * (a[j] - a[j - 1]) > 0:
			t = t - r * (a[j] - a[j - 1]) + b[j]
			if t >= max_t:
				max_t = t
	print(max_t)


for i in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	maxt = 0
	for j in range(n):
		if j == 0:
			t = 0
		else:
			t -= (a[j] - a[j - 1]) * r
			if t < 0:
				t = 0
		t += b[j]
		if t > maxt:
			maxt = t
	print(maxt)


n = int(input())
g = []
while n:
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = list(map(int, input().split()))
	t = d[0]
	m = t
	for i in range(1, a):
		t = t - (c[i] - c[i - 1]) * b
		if t < 0:
			t = 0
		t = t + d[i]
		m = max(t, m)
	g.append(m)
	n = n - 1
for i in g:
	print(i)


for t in range(int(input())):
	(n, r) = map(int, input().split())
	ts = list(map(int, input().split()))
	bs = list(map(int, input().split()))
	tension = bs[0]
	maxi = tension
	for i in range(1, n):
		tension -= (ts[i] - ts[i - 1]) * r
		if tension < 0:
			tension = 0
		tension += bs[i]
		maxi = max(tension, maxi)
	print(maxi)


T = int(input())
for i in range(0, T):
	(N, R) = map(int, input().split())
	A1 = input().split()
	B1 = input().split()
	if N == 1:
		print(int(B1[0]))
	else:
		A = [int(A1[0])]
		B = [int(B1[0])]
		C = int(B1[0])
		result = C
		for j in range(1, N):
			A.append(int(A1[j]))
			B.append(int(B1[j]))
			C = max(0, C - (A[j] - A[j - 1]) * R) + B[j]
			result = max(result, C)
		print(result)


def solve():
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.append(0)
	x = 0
	result = 0
	for i in range(0, n):
		x += b[i]
		result = max(result, x)
		x = max(0, x - r * (a[i + 1] - a[i]))
	print(result)

def main():
	for _ in range(int(input())):
		solve()
main()


t = int(input())
for i in range(t):
	(n, r) = map(int, input().split())
	ex_time = list(map(int, input().split()))
	ten_array = list(map(int, input().split()))
	tire = 0
	maxx = 0
	for i in range(n):
		tire = tire + ten_array[i]
		if tire > maxx:
			maxx = tire
		try:
			if tire - r * (ex_time[i + 1] - ex_time[i]) < 0:
				tire = 0
			else:
				tire = tire - r * (ex_time[i + 1] - ex_time[i])
		except IndexError:
			break
	print(maxx)


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


T = int(input())
for i in range(T):
	(n, r) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	i = m = x = 0
	while i < n:
		x = x + l2[i]
		if x > m:
			m = x
		i = i + 1
		if i < n:
			x = x - (l1[i] - l1[i - 1]) * r if x - (l1[i] - l1[i - 1]) * r > 0 else 0
	print(m)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	t = 0
	max1 = 0
	for i in range(n - 1):
		t += B[i]
		if t > max1:
			max1 = t
		t = max(0, t - (A[i + 1] - A[i]) * r)
	t = t + B[n - 1]
	if t > max1:
		max1 = t
	print(max1)


for i in range(int(input())):
	(n, r) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = b[0]
	x = b[0]
	for i in range(1, len(b)):
		x = x - r * (a[i] - a[i - 1])
		if x < 0:
			x = 0
		x = x + b[i]
		if m < x:
			m = x
	print(m)


T = int(input())
for i in range(T):
	(n, r) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	x = b[0]
	max_x = b[0]
	for j in range(1, n):
		x = x - r * (a[j] - a[j - 1])
		if x <= 0:
			x = 0
		x += b[j]
		if x > max_x:
			max_x = x
	print(max_x)


for _ in range(int(input())):
	(N, R) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	ans = B[0]
	x = B[0]
	for i in range(1, N, 1):
		dec = (A[i] - A[i - 1]) * R
		x = max(x - dec, 0)
		x += B[i]
		ans = max(ans, x)
	print(ans)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	ans = 0
	t = 0
	for i in range(n):
		ans += l2[i]
		t = max(ans, t)
		if i != n - 1:
			ans -= r * (l1[i + 1] - l1[i])
		if ans < 0:
			ans = 0
	print(t)