There are initially X people in a room. 

You are given an array A of length N which describes the following events:
If A_{i} ≥ 0, then A_{i} people enter the room at i-th minute. For e.g. if A_{2} = 3, then 3 people enter the room at the 2-nd minute.
If A_{i} < 0, then |A_{i}| people leave the room at i-th minute. Here |A_{i}| denotes the absolute value of A_{i}. For e.g. if A_{4} = -2, then 2 people leave the room at the 4-th minute.

Determine the maximum number of people in the room at any moment of time.

It is guaranteed in the input that at any moment of time, the number of people in the room does not become negative.

------ Input Format ------ 

- The first line will contain T - the number of test cases. Then the test cases follow.
- The first line of each test case consists of two integers N and X - the length of the array A and the number of people in the room initially.
- The second line of each test case contains N integers A_{1}, A_{2}, A_{3}, \dots A_{N}.

------ Output Format ------ 

For each testcase, output the maximum number of people in the room at any point of time.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$0 ≤ X ≤ 100$
$-100 ≤ A_{i} ≤ 100$

----- Sample Input 1 ------ 
3
5 8
0 3 3 -13 5
4 5
0 -2 2 3
3 5
-2 5 -2

----- Sample Output 1 ------ 
14
8
8

----- explanation 1 ------ 
Test case-1: In the $3$-rd minute, the room contains $8 + 0 + 3 + 3 = 14$ people which is the maximum number of people in the room at any point of time.

Test case-2: In the $4$-th minute, the room contains $5 + 0 - 2 + 2 + 3 = 8$ people which is the maximum number of people in the room at any point of time.

Test case-3: In the $2$-nd minute, the room contains $5 - 2 + 5 = 8$ people which is the maximum number of people in the room at any point of time.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Implementation


Solutions:
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	m = x
	for i in a:
		if i >= 0:
			x = x + i
			if m < x:
				m = x
		else:
			x = x + i
	print(m)


for i in range(int(input())):
	(N, I) = map(int, input().split())
	li = list(map(int, input().split()))
	maxs = I
	ans = I
	for i in li:
		ans += i
		if ans > maxs:
			maxs = ans
	print(maxs)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	p = x
	maxp = x
	for m in a:
		p += m
		maxp = max(maxp, p)
	print(maxp)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	integers = list(map(int, input().split()))
	count_max = x
	count = x
	for i in range(n):
		count += integers[i]
		if count > count_max:
			count_max = count
	print(count_max)


for T in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	lst = []
	lst.append(X)
	for i in A:
		X += i
		lst.append(X)
	print(max(lst))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	lst = []
	lst.append(x)
	for i in a:
		x += i
		lst.append(x)
	print(max(lst))


for i in range(int(input())):
	l1 = []
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l1.append(b)
	for i in l:
		b += i
		l1.append(b)
	print(max(l1))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	lis = list(map(int, input().split()))
	maxx = x
	for i in lis:
		x += i
		if x > maxx:
			maxx = x
	print(maxx)


for t in range(int(input())):
	(n, x) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	maxnum = 0
	numtem = x
	for num in l:
		numtem += num
		if maxnum <= numtem:
			maxnum = numtem
	print(max(x, maxnum))


t = int(input())
for tc in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	m = x
	for j in range(n):
		x += a[j]
		if x > m:
			m = x
	print(m)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	list1 = list(map(int, input().split()))
	max = x
	total = x
	for i in list1:
		total += i
		if total > max:
			max = total
	print(max)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	t = list(map(int, input().split()))
	s = x
	temp = s
	for i in t:
		if s + i >= temp:
			temp = s + i
			s += i
		else:
			s += i
	print(temp)


for _ in range(int(input())):
	(N, x) = map(int, input().split())
	t = list(map(int, input().split()))
	count = x
	maxval = x
	for i in range(N):
		if t[i] > 0:
			count += t[i]
			if maxval < count:
				maxval = count
		if t[i] < 0:
			count -= abs(t[i])
	print(maxval)


t = int(input())
for i in range(t):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	B = []
	sum = X
	for i in range(N):
		if A[i] >= 0:
			sum = sum + A[i]
			B.append(sum)
		else:
			sum = sum + A[i]
			B.append(sum)
	M = X
	p = max(B)
	print(max(M, p))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	sum = x
	b = []
	for i in range(n):
		if l[i] >= 0:
			sum = sum + l[i]
			b.append(sum)
		else:
			sum = sum + l[i]
			b.append(sum)
	m = x
	p = max(b)
	print(max(m, p))


def answer():
	(n, x) = map(int, input().split())
	s = x
	l = list(map(int, input().split()))
	m = x
	for i in l:
		s = s + i
		m = max(m, s)
	print(m)
for test in range(int(input())):
	answer()


t = int(input())
while t:
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))[:n]
	l = [x]
	for i in range(n):
		x += arr[i]
		l.append(x)
	print(max(l))
	t -= 1


def max_people(A, p):
	current_people = p
	max_people = p
	for i in range(len(A)):
		current_people += A[i]
		max_people = max(max_people, current_people)
	return max_people
for i in range(int(input())):
	(m, x) = map(int, input().split())
	A = list(map(int, input().split()))
	print(max_people(A, x))


testcases = int(input())
while testcases > 0:
	(N, X) = map(int, input().split())
	li = list(map(int, input().split()))
	maxi = X
	sum1 = X
	for i in range(len(li)):
		sum1 += li[i]
		maxi = max(sum1, maxi)
		if sum1 < 0:
			sum1 = X
	print(maxi)
	testcases -= 1


T = int(input())
for _ in range(T):
	(n, x) = map(int, input().split())
	A = list(map(int, input().split()))
	c = []
	c.append(x)
	for i in A:
		c.append(c[len(c) - 1] + i)
	print(max(c))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l1.append(x)
	for x in l:
		l1.append(l1[len(l1) - 1] + x)
	print(max(l1))


for i in range(int(input())):
	(x, y) = map(int, input().split())
	a = [int(x) for x in input().split()]
	m = y
	for j in range(x):
		if sum(a[:j + 1]) + y > m:
			m = sum(a[:j + 1]) + y
	print(m)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = [int(x) for x in input().split()]
	s = b
	m = b
	for i in c:
		s += i
		if s > m:
			m = s
	print(m)


t = int(input())
for i in range(0, t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	present = x
	maxim = x
	for j in range(len(a)):
		if a[j] > 0 or a[j] < 0:
			present = present + a[j]
		if present > maxim:
			maxim = present
	print(maxim)


for i in range(0, int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	s = 0
	for j in range(0, N):
		s = s + A[j]
		A[j] = s
	m = max(A)
	if m < 0:
		m = 0
	print(m + X)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	l.append(x)
	for y in a:
		if y >= 0:
			x += y
			l.append(x)
		else:
			x -= abs(y)
			l.append(x)
	print(max(l))


def akash():
	(a, t1) = [int(t1t1) for t1t1 in input().split()]
	l = [int(t1) for t1 in input().split()]
	sol = t1
	res = t1
	for i in l:
		res += i
		sol = max(sol, res)
	print(sol)
z = 1
z = int(input())
for _ in range(z):
	akash()


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	sum1 = x
	sum2 = x
	for j in a:
		sum1 += j
		if sum1 > sum2:
			sum2 = sum1
	print(sum2)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	temp = [x]
	te = x
	a = list(map(int, input().split()))
	for j in a:
		te += j
		temp.append(te)
	print(max(temp))


for _ in range(int(input())):
	(N, X) = map(int, input().split())
	pplent = list(map(int, input().split()))
	s = 0
	ppl = []
	for i in range(N):
		s = s + pplent[i]
		ppl.append(s)
	if X > X + max(ppl):
		print(X)
	else:
		print(X + max(ppl))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = x
	l = []
	l.append(sum)
	for i in range(len(a)):
		sum = sum + a[i]
		l.append(sum)
	print(max(l))


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = eval(f"[{input().replace(' ', ', ')}]")
	mx = x
	y = 0
	for i in range(n):
		y += a[i]
		if mx < y + x:
			mx = y + x
	print(mx)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = eval(f"[{input().replace(' ', ', ')}]")
	mx = x
	for i in range(n):
		s = sum(a[:i + 1])
		if mx < s + x:
			mx = s + x
	print(mx)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	li = list(map(int, input().split()))
	s = x
	for i in range(n):
		a = sum(li[:i + 1])
		if a + x > s:
			s = a + x
	print(s)


for _ in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	ma = X
	for i in range(N):
		su = sum(A[:i + 1])
		if su + X > ma:
			ma = su + X
	print(ma)


t = int(input())
while t > 0:
	(n, x) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	m = [x]
	for i in range(n):
		x = x + a[i]
		m.append(x)
	print(max(m))
	t = t - 1


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	m = [x]
	for item in a:
		x += item
		m.append(x)
	print(max(m))


for o in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	maxx = x
	asum = x
	for i in a:
		asum += i
		if asum > maxx:
			maxx = asum
	print(maxx)


t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = []
	s = b
	l.append(s)
	for i in range(len(arr)):
		s = s + arr[i]
		l.append(s)
	print(max(l))
	t = t - 1


t = int(input())
while t:
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	l = x
	for i in a:
		x += i
		l = max(l, x)
	print(l)
	t -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = k
	for i in l:
		k = k + i
		x = max(x, k)
	print(x)


for T in range(int(input())):
	(n, x) = map(int, input().split())
	li = list(map(int, input().split()))
	(v, w) = (x, 0)
	for i in li:
		x = x + i
		if x >= v:
			v = x
			w = i
	print(v)


t = int(input())
while t != 0:
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	k = []
	k.append(x)
	for i in range(len(arr)):
		x = x + arr[i]
		k.append(x)
	print(max(k))
	t -= 1


test = int(input())
for i in range(test):
	(number, inital) = map(int, input().split())
	List = list(map(int, input().split()))
	result = inital
	total = inital
	for i in List:
		result = result + i
		total = max(result, total)
	print(total)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	l.append(x + a[0])
	for i in range(1, n):
		l.append(a[i] + l[i - 1])
	print(max(x, max(l)))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = k
	j = 0
	m = []
	while j < n:
		sum += a[j]
		m.append(sum)
		j += 1
	print(max(max(m), k))


for tc in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	maxx = x
	for i in a:
		x += i
		if maxx < x:
			maxx = x
	print(maxx)


t = int(input())
for ni in range(t):
	(n, x) = map(int, input().split())
	l = [int(i) for i in input().split()]
	l1 = [0] * n
	l1[0] = x + l[0]
	for i in range(1, n):
		l1[i] = l1[i - 1] + l[i]
	print(max(x, max(l1)))


t = int(input())
while t != 0:
	(n, p) = map(int, input().split())
	l = list(map(int, input().split()))
	m = p
	for x in l:
		p += x
		if p > m:
			m = p
	print(m)
	t -= 1


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	lst = list(map(int, input().split()))
	sum1 = 0
	for i in range(a):
		if sum(lst[0:i + 1]) > sum1:
			sum1 = sum(lst[0:i + 1])
	print(sum1 + b)


t = int(input())
for i in range(t):
	(s, k) = (0, 0)
	(n, x) = map(int, input().split())
	s = x
	l = list(map(int, input().split()))
	for i in range(n):
		s += l[i]
		if s >= k and s > x:
			k = s
		else:
			continue
	if k > x:
		print(k)
	else:
		print(x)


for t in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for i in range(n):
		if sum(l[0:i + 1]) > s:
			s = sum(l[0:i + 1])
	print(s + x)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	total = x
	max_total = 0
	l = []
	for j in range(n):
		total += lst[j]
		l.append(total)
	if x > max(l):
		print(x)
	else:
		print(max(l))


for _ in range(int(input())):
	(a, n) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.insert(0, n)
	temp = []
	for i in range(1, len(lst)):
		temp.append(sum(lst[i::-1]))
	if max(temp) > n:
		print(max(temp))
	else:
		print(n)


T = int(input())
for t in range(T):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	m = []
	count = x
	for i in range(n):
		count = count + a[i]
		m.append(count)
	if x > max(m):
		print(x)
	else:
		print(max(m))


t = int(input())
for dummy in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	maxi = x
	for v in a:
		x += v
		if x > maxi:
			maxi = x
	print(maxi)


T = int(input())
for i in range(T):
	(N, X) = map(int, input().split())
	A = input().split()
	total = [X]
	for x in range(N):
		X += int(A[x])
		total.append(X)
	MAX = 0
	for y in range(N + 1):
		MAX = max(MAX, total[y])
	print(MAX)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	li = list(map(int, input().split()))
	maxy = x
	for i in range(n):
		x += li[i]
		if maxy < x:
			maxy = x
	print(maxy)


for _ in range(int(input())):
	(a, n) = map(int, input().split())
	lst = list(map(int, input().split()))
	temp = []
	var = n
	for i in range(len(lst)):
		var += lst[i]
		temp.append(var)
	if max(temp) > n:
		print(max(temp))
	else:
		print(n)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	l = []
	k = x
	for i in range(len(lst)):
		x = x + lst[i]
		l.append(x)
	if k > max(l):
		print(k)
	else:
		print(max(l))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	l = [x]
	b = x
	for j in a:
		b += j
		l += [b]
	print(max(l))