Vishal loves running. He often visits his favourite Nehru Park and runs for very long distances. On one such visit he found that the number of girls in the park was unusually high. Now he wants to use this as an opportunity to impress a large number of girls with his awesome speed. 

The track on which he runs is an $\text{N}$ kilometres long straight path. There are $\mathbf{a_{i}}$ girls standing within the $\text{ith}$ kilometre of this path. A girl will be impressed only if Vishal is running at his maximum speed when he passes by her. But he can run at his best speed only for a single continuous stretch of $\text{K}$ kilometres. Now Vishal wants to know what is the maximum number of girls that he can impress.

------ Input ------
First line of the input contains the number of testcases $\text{T}$.

For each test case,

First line contains two space-separated integers $\text{N}$ and $\text{K}$, the length of the track and the maximum distance he can run at his best speed.

Second line contains N space-separated integers, the number of girls within each kilometre of the track.

------ Output ------
For each test case print one line containing an integer, denoting the maximum number of girls Vishal can impress.

------ Constraints  ------
$1 ≤ \text{T} ≤ 10$

$1 ≤ \text{K} ≤ \text{N} ≤ 100$ 

$1 ≤ \mathbf{a_{i}} ≤ 100$ 

----- Sample Input 1 ------ 
1
7 2
2 4 8 1 2 1 8
----- Sample Output 1 ------ 
12
----- explanation 1 ------ 
He can impress 4+8=12 girls if he runs at his best speed between the 2nd and the 3rd kilometre, inclusive.

Difficulty: EASY
Tags: Amortized analysis

Range queries

Complete search
Skill types: Amortized analysis

Range queries

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	max1 = 0
	for i in range(n - 1):
		if sum(a[i:i + k]) > max1:
			max1 = sum(a[i:i + k])
	print(max1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	girls = list(map(int, input().split()))
	res = 0
	for win in range(n - 1):
		if sum(girls[win:win + k]) > res:
			res = sum(girls[win:win + k])
	else:
		print(res)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	maximum = 0
	for i in range(n - 1):
		y = sum(x[i:i + k])
		maximum = max(maximum, y)
	print(maximum)


for _ in range(int(input())):
	ls = []
	(n, k) = map(int, input().split())
	girls = [int(i) for i in input().split()][:n]
	for i in range(n - k + 1):
		a = 0
		for j in range(k):
			a += girls[i]
			i += 1
		ls.append(a)
	print(max(ls))


t = int(input())
for i in range(0, t):
	b = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = []
	x = 0
	y = b[0]
	for i in range(0, b[0]):
		x = 0
		for j in range(0, b[1]):
			if i + j < b[0]:
				x = a[i + j] + x
		c.append(x)
	c.sort(reverse=True)
	print(c[0])


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


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	s = []
	for l in range(len(a) - 1):
		p = sum(a[l:k + l])
		s.append(p)
	print(max(s))


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


for j in range(int(input())):
	(n, k) = map(int, input().split())
	girls = list(map(int, input().split()))
	res = 0
	for i in range(n - 1):
		if sum(girls[i:i + k]) > res:
			res = sum(girls[i:i + k])
	else:
		print(res)


t = int(input())
l1 = []
for i in range(t):
	(n, k) = [int(a) for a in input().split()]
	l = list(map(int, input().split()))
	res = 0
	for i in range(n - k + 1):
		if sum(l[i:i + k]) > res:
			res = sum(l[i:i + k])
	print(res)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = 0
	for i in range(n - k + 1):
		s = sum(l[i:i + k])
		m = max(m, s)
	print(m)


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


import sys
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = -sys.maxsize
	for i in range(n - k + 1):
		s = sum(l[i:i + k])
		if m < s:
			m = s
	print(m)


t = int(input())
while t > 0:
	t = t - 1
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ab = sum(a[:k])
	abb = ab
	for i in range(1, n - k + 1):
		ab = ab - a[i - 1] + a[i + k - 1]
		if ab > abb:
			abb = ab
	print(abb)


T = int(input())
for i in range(0, T):
	lst = []
	(N, K) = map(int, input().split())
	girls = list(map(int, input().split()))
	for i in range(0, len(girls)):
		if len(girls[i:i + K]) == K:
			lst.append(sum(girls[i:i + K]))
	print(max(lst))


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	ans = 0
	for i in range(n):
		if sum(a[i:i + k]) > ans:
			ans = sum(a[i:i + k])
	print(ans)


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


for _ in range(int(input())):
	(k, r) = map(int, input().split())
	x = list(map(int, input().split()))
	ans = []
	for i in range(len(x) - 1):
		ans.append(sum(x[i:r + i]))
	print(max(ans))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	sm = 0
	for i in range(len(a) - 1):
		if sm < sum(a[i:k + i]):
			sm = sum(a[i:k + i])
	print(sm)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	k = []
	for j in range(a - b + 1):
		d = 0
		for x in range(j, j + b):
			d += c[x]
		k.append(d)
	print(max(k))


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


for i in range(int(input())):
	t = input().split()
	(n, k) = (int(t[0]), int(t[1]))
	a = list(map(int, input().split()))
	ans = 0
	d = {}
	for i in range(len(a) - k + 1):
		d[i] = sum(a[i:i + k])
	ans = 0
	for key in d:
		ans = max(ans, d[key])
	print(ans)


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	max = 0
	for i in range(n):
		sum = 0
		for j in range(k):
			if i + j < n:
				sum += arr[i + j]
		if sum > max:
			max = sum
	print(max)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	glist = list(map(int, input().split()))
	maxg = 0
	for i in range(0, n - k + 1):
		gsum = 0
		for g in glist[i:i + k]:
			gsum += g
		if gsum > maxg:
			maxg = gsum
	print(maxg)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	p = list(map(int, input().split()))
	su = 0
	for i in range(y):
		su += p[i]
	maxi = su
	for i in range(y, x):
		su += p[i] - p[i - y]
		maxi = max(su, maxi)
	print(maxi)


for t in range(int(input())):
	(length, speed) = map(int, input().split())
	girls = list(map(int, input().split()))[:length]
	result = []
	for i in range(length - 1):
		result.append(sum(girls[i:i + speed]))
	print(max(result))


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	maxm = arr[0]
	curr = 0
	(i, j) = (0, k - 1)
	while j < len(arr):
		curr = sum(arr[i:j + 1])
		maxm = max(curr, maxm)
		i += 1
		j += 1
	print(maxm)


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


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	i = 0
	k = 0
	p = y
	while i <= len(a) - y:
		s = 0
		j = i
		while j < p:
			s += a[j]
			j += 1
		if s > k:
			k = s
		i += 1
		p += 1
	print(k)


n = int(input())
m = 0
while m < n:
	(a, b) = map(int, input().split())
	x = list(map(int, input().split(' ')))
	sum1 = 0
	for i in range(a - 1):
		if sum(x[i:i + b]) > sum1:
			sum1 = sum(x[i:i + b])
	print(sum1)
	m += 1


q = int(input())
for i in range(q):
	w = 0
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	for i in range(n - 1):
		if sum(s[i:i + k]) > w:
			w = sum(s[i:i + k])
	print(w)


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


for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ls_sum = 0
	for i in range(n + 1 - k):
		sum = 0
		for j in range(k):
			sum += a[i + j]
		if sum > ls_sum:
			ls_sum = sum
	print(ls_sum)


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


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	L = []
	for i in range(0, n):
		r = sum(l[i:i + k])
		L.append(r)
	print(max(L))


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	girls = list(map(int, input().split()))
	res = 0
	for i in range(x - 1):
		if sum(girls[i:i + y]) > res:
			res = sum(girls[i:i + y])
	print(res)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	temp = 0
	for j in range(N - 1):
		if sum(A[j:j + K]) > temp:
			temp = sum(A[j:j + K])
	print(temp)


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	res = []
	for i in range(n - 1):
		ans = sum(l[i:i + k])
		res.append(ans)
	print(max(res))


def fun(l, k):
	sum = 0
	for i in range(0, len(l) - k + 1):
		temp = 0
		for j in range(i, k + i):
			temp = temp + l[j]
		if temp > sum:
			sum = temp
	return sum
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	print(fun(l, k))


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	x = 0
	sums = 0
	for j in range(n - k + 1):
		for m in range(j, j + k):
			sums += l[m]
		x = max(sums, x)
		sums = 0
	print(x)


T = int(input())
for _ in range(T):
	track = input().split()
	(N, K) = map(int, track)
	girl_locations = input().split()
	girl_arr = list(map(int, girl_locations))
	max_girls = 0
	for i in range(N):
		_max = sum(girl_arr[i:i + K])
		if max_girls < _max:
			max_girls = _max
	print(max_girls)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	max_gl = 0
	for i in range(n):
		temp_max_gl = sum(arr[i:i + k])
		if max_gl < temp_max_gl:
			max_gl = temp_max_gl
	print(max_gl)


for i in range(int(input())):
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	a = 0
	for i in range(len(m) - l[1] + 1):
		b = m[i]
		for k in range(1, l[1]):
			b = b + m[i + k]
		if b >= a:
			a = b
		else:
			continue
	print(a)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	r = 0
	for j in range(n - 1):
		if sum(a[j:j + k]) > r:
			r = sum(a[j:j + k])
	print(r)


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	g = 0
	for i in range(n - k + 1):
		s = sum(a[i:i + k])
		g = max(g, s)
	print(g)


for ________cases________ in range(int(input())):
	(N, K) = map(int, input().split())
	L = list(map(int, input().split()))
	girls = 0
	for i in range(N - K + 1):
		S = sum(L[i:i + K])
		girls = max(girls, S)
	print(girls)


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	s = 0
	m = 0
	for i in range(0, n - k + 1):
		for j in range(i, i + k):
			s = s + ar[j]
		if s > m:
			m = s
		s = 0
	print(m)


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


def max_girls_impressed(n, k, a):
	max_impressed = 0
	curr_impressed = sum(a[:k])
	max_impressed = curr_impressed
	for i in range(k, n):
		curr_impressed += a[i] - a[i - k]
		max_impressed = max(max_impressed, curr_impressed)
	return max_impressed
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = max_girls_impressed(n, k, a)
	print(ans)


t = int(input())
for i in range(1, t + 1):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	j = []
	for i in range(0, len(l)):
		p = l[i:i + y]
		k = sum(p)
		j.append(k)
	print(max(j))


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