You are walking through a parkway near your house. The parkway has $n+1$ benches in a row numbered from $1$ to $n+1$ from left to right. The distance between the bench $i$ and $i+1$ is $a_i$ meters.

Initially, you have $m$ units of energy. To walk $1$ meter of distance, you spend $1$ unit of your energy. You can't walk if you have no energy. Also, you can restore your energy by sitting on benches (and this is the only way to restore the energy). When you are sitting, you can restore any integer amount of energy you want (if you sit longer, you restore more energy). Note that the amount of your energy can exceed $m$.

Your task is to find the minimum amount of energy you have to restore (by sitting on benches) to reach the bench $n+1$ from the bench $1$ (and end your walk).

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($1 \le n \le 100$; $1 \le m \le 10^4$).

The second line of the test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$), where $a_i$ is the distance between benches $i$ and $i+1$.


-----Output-----

For each test case, print one integer — the minimum amount of energy you have to restore (by sitting on benches) to reach the bench $n+1$ from the bench $1$ (and end your walk) in the corresponding test case.


-----Examples-----

Input
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
Output
3
8
0


-----Note-----

In the first test case of the example, you can walk to the bench $2$, spending $1$ unit of energy, then restore $2$ units of energy on the second bench, walk to the bench $3$, spending $2$ units of energy, restore $1$ unit of energy and go to the bench $4$.

In the third test case of the example, you have enough energy to just go to the bench $6$ without sitting at all.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	g = sum(arr)
	if k >= g:
		print(0)
	else:
		print(g - k)


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

def getint():
	return int(input())
for t in range(getint()):
	(n, m) = getarr()
	a = getarr()
	s = sum(a)
	print(max(0, s - m))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(max(0, sum(arr) - m))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	r = sum(a)
	if r <= m:
		print(0)
	else:
		print(r - m)


T = int(input())
for t in range(T):
	(n, m) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	print(max(sum(A) - m, 0))


import math
import collections
import itertools
import functools

def fun(t):
	(n, m) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	if sum(arr) - m < 0:
		print('0')
		return
	print(sum(arr) - m)
for tc in range(int(input())):
	fun(tc)


t = int(input())
for _ in range(t):
	(n, m) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	s = sum(a)
	if m < s:
		print(s - m)
	else:
		print(0)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	add = 0
	for i in range(n):
		if m >= arr[i]:
			m -= arr[i]
		else:
			add += arr[i] - m
			m = 0
	print(add)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	ans = sum(x) - m
	if ans <= 0:
		print(0)
	else:
		print(ans)


import sys
sys.setrecursionlimit(2 * 10 ** 6)

def test():
	pass

def main():
	N = int(input())
	for _ in range(N):
		(n, m) = map(int, input().split())
		arr = list(map(int, input().split()))
		print(max(0, sum(arr) - m))

def init():
	import sys
	import os
	if 'DOCKER_HOST' in os.environ:
		test()
		sys.stdin = open('test.txt')
init()
main()


def solve():
	(n, m) = map(int, input().split())
	s = sum([int(i) for i in input().split()])
	res = max(0, s - m)
	print(res)
	return

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


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	ls = list(map(int, input().split()))
	l = sum(ls)
	if y >= l:
		print(0)
	else:
		print(l - y)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	v = input().split()
	for j in range(n):
		ans += int(v[j])
	print(max(0, ans - m))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	if sum(l) >= m:
		print(sum(l) - m)
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = [int(x) for x in input().split()]
	if sum(l) < m:
		print(0)
	else:
		print(sum(l) - m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	sm = sum(lst)
	print(max(0, sm - m))


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	benches = n + 1
	i = 0
	if m >= sum(a):
		print(0)
	else:
		while True:
			if m - a[i] >= 0:
				m = m - a[i]
				i += 1
			else:
				break
		rest = 0
		while i < len(a):
			rest += a[i]
			i += 1
		print(rest - m)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	energies = [int(x) for x in input().split()]
	totalenergies = sum(energies)
	if m >= totalenergies:
		print(0)
	else:
		print(abs(totalenergies - m))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = map(int, input().split())
	print(max(0, sum(a) - m))


def walk(A, n, m):
	sm = 0
	for i in range(n):
		sm += A[i]
	return max(sm - m, 0)
tests = int(input())
for _ in range(tests):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	print(walk(A, n, m))


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = list(map(int, input().split()))
	A = sum(a)
	d = A - m
	if d >= 0:
		print(d)
	else:
		print(0)


t = int(input())
(n, m) = (0, 0)
for i in range(t):
	(n, m) = map(int, input().split())
	nums = list(map(int, input().split()))
	s = 0
	for i in range(len(nums)):
		if m >= nums[i]:
			m -= nums[i]
		else:
			s += nums[i] - m
			m = 0
	print(s)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	a = sum(list(map(int, input().split())))
	print(max(0, a - m))
	t -= 1


t = int(input())
while t != 0:
	(n, x) = input().split()
	n = int(n)
	x = int(x)
	l = list(map(int, input().split()))
	m = sum(l) - x
	if m < 0:
		print(0)
	else:
		print(m)
	t = t - 1


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	total_energy = sum(l)
	if m >= total_energy:
		print(0)
	else:
		print(total_energy - m)


k = int(input())
for i in range(k):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	lst = list(map(int, input().split()))
	total = 0
	for ele in range(0, len(lst)):
		total = total + lst[ele]
	if total > m:
		print(total - m)
	else:
		print('0')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	S = sum(A)
	print(S - m if S >= m else '0')


def solution(_):
	(n, energy) = map(int, input().split())
	benches = list(map(int, input().split()))
	print(max(0, sum(benches) - energy))
for _ in range(int(input())):
	solution(_)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	(n, m) = (a[0], a[1])
	benches = list(map(int, input().split()))
	energy = sum(benches)
	if energy <= m:
		print(0)
	else:
		print(energy - m)


import sys
T = int(sys.stdin.readline().rstrip())
for _ in range(T):
	(n, m) = map(int, sys.stdin.readline().split())
	distance_list: list = list(map(int, sys.stdin.readline().split()))
	sum_of_distance: int = sum(distance_list)
	need_energy = sum_of_distance - m
	print(need_energy if need_energy > 0 else 0)


t = int(input())
for i in range(t):
	b = input().split()
	m = int(b[0])
	n = int(b[1])
	a = input().split()
	for j in range(len(a)):
		a[j] = int(a[j])
	s = sum(a)
	if s > n:
		print(s - n)
	else:
		print(0)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	k = 0
	for i in range(n):
		k = k + l[i]
	if k <= m:
		print(0)
	else:
		print(k - m)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	d = sum(lst)
	end = d - m
	if end <= 0:
		print(0)
	else:
		print(end)


def pw(a: list, n: int, m: int) -> int:
	s = sum(a)
	if m >= s:
		return 0
	else:
		return s - m
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	print(pw(a, n, m))
	t -= 1


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	(n, m) = (arr[0], arr[1])
	arrBench = list(map(int, input().split()))
	summ = sum(arrBench)
	if m < summ:
		print(summ - m)
	else:
		print(0)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = 0
	l1 = list(map(int, input().split()))
	for i in range(n):
		s += l1[i]
	if s > m:
		print(s - m)
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	energy = sum(a) - m
	if energy <= 0:
		energy = 0
	print(energy)


TestCases = int(input())
for i in range(0, TestCases):
	BenchEnergy = input().split()
	Benches = input().split()
	answer = 0
	for i in range(0, len(Benches)):
		answer += int(Benches[i])
	answer -= int(BenchEnergy[1])
	if answer <= 0:
		print(0)
	else:
		print(answer)


T = int(input())
for i in range(0, T):
	(n, m) = map(int, input().split())
	print(max(0, sum(map(int, input().split())) - m))


cnt = int(input())
for i in range(cnt):
	cases = list(map(int, input().split()))
	benches = list(map(int, input().split()))
	print(max(0, sum(benches) - cases[1]))


def run_test_case():
	(n, m) = [int(num) for num in input().split()]
	distances_between_benches = [int(num) for num in input().split()]
	assert len(distances_between_benches) == n
	e = 0
	for i in range(n):
		if distances_between_benches[i] >= m:
			e += distances_between_benches[i] - m
			m = 0
		else:
			m -= distances_between_benches[i]
		if m == 0:
			break
	e += sum(distances_between_benches[i + 1:])
	return e

def run():
	energies_to_restore = []
	for i in range(int(input())):
		energies_to_restore.append(run_test_case())
	print('\n'.join([str(e) for e in energies_to_restore]))
run()


test = int(input())
for t in range(test):
	a = list(map(int, input().split()))
	n = a[0]
	m = a[1]
	finish = False
	b = list(map(int, input().split()))
	while m > b[0]:
		m -= b[0]
		b.pop(0)
		if len(b) == 0:
			finish = True
			break
	if finish:
		print(0)
	else:
		print(sum(b) - m)


t = int(input(''))
for z in range(t):
	a = []
	(n, m) = map(int, input('').split())
	a = list(map(int, input('').split()))[:n]
	su = sum(a)
	if su <= m:
		print(0)
	else:
		print(su - m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ar = map(int, input().split())
	t = sum(ar)
	if t <= m:
		print(0)
	else:
		print(t - m)


t = int(input())
while t > 0:
	t -= 1
	total = 0
	m = list(map(int, input().split()))
	l = list(map(int, input().split()))
	for item in l:
		total += int(item)
	if m[1] < total:
		print(total - m[1])
	else:
		print(0)


import sys

def rall():
	return [x.strip() for x in sys.stdin.readlines()]

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	(n, m) = map(int, rl().split(' '))
	array = list(map(int, rl().split(' ')))
	tot = sum(array)
	pr(max(tot - m, 0))


a = int(input())
for i in range(a):
	(b, c) = map(int, input().split())
	d = list(map(int, input().split()))
	t = sum(d)
	if t <= c:
		print(0)
	else:
		print(t - c)


T = int(input())
for t in range(0, T):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	a = input().split()
	a = list(map(int, a))
	print(max(sum(a) - m, 0))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	print(max(0, sum(A) - m))


t = input()
tests = int(t)
for i in range(0, tests):
	s = input()
	(n, m) = s.split()
	n = int(n)
	m = int(m)
	s = input().split()
	arr = [int(x) for x in s]
	sum = 0
	for num in arr:
		sum = sum + num
	print(max(sum - m, 0))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = 0
	a = list(map(int, input().split()))
	for ai in a:
		d = d + ai
	print(d - m) if d - m > 0 else print(0)


cases = int(input())
for case in range(0, cases):
	key = tuple(input().split())
	n = int(key[0])
	m = int(key[1])
	_list = input().split()
	s = sum(map(int, _list))
	print(max(0, s - m))


def solve_case(case_arg1, case_arg2):
	(n, m) = tuple(map(int, case_arg1.split()))
	a = list(map(int, case_arg2.split()))
	return max(sum(a) - m, 0)

def main():
	N_cases = int(input())
	for _ in range(N_cases):
		case_arg1 = input()
		case_arg2 = input()
		print(solve_case(case_arg1, case_arg2))
main()


N = int(input())
for i in range(N):
	(n, m) = map(int, input().split())
	s = sum(list(map(int, input().split())))
	if s <= m:
		print(0)
	else:
		print(s - m)


l = lambda : map(int, input().split())
(i,) = l()
exec(i * 'n,m=l();print(max(0,sum(l())-m));')


T = int(input())
for _ in range(T):
	t = input().split()
	n = int(t[0])
	m = int(t[1])
	t = input().split()
	a = []
	for i in range(n):
		a.append(int(t[i]))
	s = sum(a)
	print(max(0, s - m))


t = int(input())
for k in range(t):
	(n, m) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	sum_val = sum(arr)
	if m < sum_val:
		print(sum_val - m)
	else:
		print('0')


n = int(input())
res = []
for i in range(n):
	(m, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	s = sum(a)
	if s - k > 0:
		res.append(s - k)
	else:
		res.append(0)
for i in res:
	print(i)


for j in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	a = list(map(int, input().split()))
	suml = 0
	for k in range(n):
		suml = suml + a[k]
	if m >= suml:
		print('0')
		continue
	if suml > m:
		print(suml - m)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	T = list(map(int, input().split()))
	if sum(T) <= y:
		m = 0
	else:
		m = sum(T) - y
	print(m)


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


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a_list = list(map(int, input().split()))
	sum_a = sum(a_list)
	if sum_a > m:
		print(sum_a - m)
	else:
		print(0)


k = lambda : map(int, input().split())
(t,) = k()
exec(t * 'n,m=k();print(max(0,sum(k())-m));')


n = int(input())
summ = 0
for i in range(n):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	summ = sum(c)
	if summ > b:
		print(summ - b)
	else:
		print(0)


t = int(input())
for i in range(t):
	s = 0
	(x, y) = map(int, input().split())
	z = list(map(int, input().split()))
	for j in range(x):
		s += z[j]
	if y >= s:
		print('0')
	else:
		print('%i' % (s - y))


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	list_an = list(map(int, input().split()))
	sum_of_ans = 0
	for j in list_an:
		sum_of_ans += j
	if sum_of_ans <= m:
		print(0)
	else:
		print(sum_of_ans - m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	k = list(map(int, input().split()))
	l = sum(k) - m
	if l > 0:
		print(l)
	else:
		print(0)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	energy = 0
	arr = list(map(int, input().split()))
	for j in range(n):
		if arr[j] > m:
			energy += arr[j] - m
			m = 0
		else:
			m -= arr[j]
	print(energy)


t = int(input())
for i in range(t):
	(n, m) = (int(num) for num in input().split())
	a = list((int(n) for n in input().split(' ')))
	if sum(a) <= m:
		print(0)
	else:
		print(sum(a) - m)


n = int(input())
for i in range(n):
	(l, r) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if r >= sum(arr):
		print(0)
	else:
		print(sum(arr) - r)


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	energy = 0
	for ai in a:
		if m >= ai:
			m = m - ai
		else:
			energy += ai - m
			m = 0
	print(energy)


def extract_energy():
	(n, energy) = list(map(int, input().split()))
	return (n, energy)

def restore(energy):
	totalpath = sum(list(map(int, input().split())))
	if energy < totalpath:
		restore_en = totalpath - energy
	else:
		restore_en = 0
	return restore_en
for i in range(int(input())):
	print(restore(extract_energy()[1]))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = sum(list(map(int, input().split())))
	if s > m:
		print(s - m)
	else:
		print(0)


t = int(input())
for _ in range(t):
	lst = input().split()
	n = int(lst[0])
	m = int(lst[1])
	lst = input().split()
	sm = 0
	for x in lst:
		sm += int(x)
	if sm - m >= 0:
		print(sm - m)
	else:
		print(0)


def submain(n, m, a):
	totaldistance = sum(a)
	if m >= totaldistance:
		return 0
	else:
		return totaldistance - m
n = int(input())
out = []
for i in range(n):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	x = submain(n, m, a)
	out.append(x)
for o in out:
	print(o)


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	sum = 0
	for i in a:
		sum = sum + i
	m = max(0, sum - m)
	print(m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [*map(int, input().split())]
	ans = sum(a) - m
	print(ans if ans > 0 else 0)


t = int(input())
for i in range(t):
	(n, m) = input().split()
	L = [int(a) for a in input().split(' ', int(n) - 1)]
	if int(m) >= sum(L):
		print(0)
	else:
		print(sum(L) - int(m))


for _ in [0] * int(input()):
	(x, y) = input().split()
	c = sum(list(map(int, input().split())))
	print(int(y) > c and '0' or c - int(y))