The enchanted forest got its name from the magical mushrooms growing here. They may cause illusions and generally should not be approached.

—Perfect Memento in Strict Sense

Marisa comes to pick mushrooms in the Enchanted Forest.

The Enchanted forest can be represented by $n$ points on the $X$-axis numbered $1$ through $n$. Before Marisa started, her friend, Patchouli, used magic to detect the initial number of mushroom on each point, represented by $a_1,a_2,\ldots,a_n$.

Marisa can start out at any point in the forest on minute $0$. Each minute, the followings happen in order:

She moves from point $x$ to $y$ ($|x-y|\le 1$, possibly $y=x$).

She collects all mushrooms on point $y$.

A new mushroom appears on each point in the forest.

Note that she cannot collect mushrooms on minute $0$.

Now, Marisa wants to know the maximum number of mushrooms she can pick after $k$ minutes.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10 ^ 5$, $1\le k \le 10^9$) — the number of positions with mushrooms and the time Marisa has, respectively.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the initial number of mushrooms on point $1,2,\ldots,n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$.


-----Output-----

For each test case, print the maximum number of mushrooms Marisa can pick after $k$ minutes.


-----Examples-----

Input
4
5 2
5 6 1 2 3
5 7
5 6 1 2 3
1 2
999999
5 70000
1000000000 1000000000 1000000000 1000000000 1000000000
Output
12
37
1000000
5000349985


-----Note-----

Test case 1:

Marisa can start at $x=2$. In the first minute, she moves to $x=1$ and collect $5$ mushrooms. The number of mushrooms will be $[1,7,2,3,4]$. In the second minute, she moves to $x=2$ and collects $7$ mushrooms. The numbers of mushrooms will be $[2,1,3,4,5]$. After $2$ minutes, Marisa collects $12$ mushrooms.

It can be shown that it is impossible to collect more than $12$ mushrooms.

Test case 2:

This is one of her possible moving path:

$2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$

It can be shown that it is impossible to collect more than $37$ mushrooms.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Complete search

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k <= n:
		lps = ans = 0
		for i in range(n):
			lps += arr[i]
			if i >= k:
				lps -= arr[i - k]
			ans = max(ans, lps)
		return ans + k * (k - 1) // 2
	else:
		ans = sum(arr) + (k - 1 + k - 1 - n + 1) * n // 2
		return ans
for _ in range(int(input())):
	print(solve())


import sys

def solve():
	inp = sys.stdin.readline
	(n, k) = map(int, inp().split())
	a = list(map(int, inp().split()))
	m = min(n, k)
	s = 0
	for i in range(m):
		s += a[i]
	best = s
	for i in range(m, n):
		s += a[i]
		s -= a[i - m]
		best = max(best, s)
	print(best + m * (m - 1) // 2 + (k - m) * m)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from sys import stdin
input = stdin.readline

def ii():
	return int(input())

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

def maxSubArraySum(a, size):
	n = len(a)
	s = 0
	for i in range(size):
		s += a[i]
	ans = s
	for i in range(size, n):
		s += a[i] - a[i - size]
		ans = max(ans, s)
	return ans
for _ in range(ii()):
	(n, k) = li()
	a = li()
	if k <= n:
		print(maxSubArraySum(a, k) + k * (k - 1) // 2)
		continue
	if n == 1:
		print(a[0] + k - 1)
		continue
	ans = sum(a)
	incr = k - n + 2
	ans += 1 + 2 * (incr - 2)
	for i in range(2, n):
		ans += incr
		incr += 1
	print(ans)


from random import getrandbits
RANDOM = getrandbits(32)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM
T = int(input())
q = []
for i in range(T):
	a = input().split()
	(n, k) = (int(a[0]), int(a[1]))
	data = [int(i) for i in input().split()]
	q.append((n, k, data))

def solve(n, k, data):
	if n >= k:
		addi = 0
		sums = 0
		for i in range(k):
			addi += i
			sums += data[i]
		ans = max(sums, 0)
		for j in range(k, n):
			sums = sums - data[j - k] + data[j]
			ans = max(sums, ans)
		print(ans + addi)
	else:
		stay = k - n
		ans = 0
		for (idx, i) in enumerate(data):
			ans += idx + stay + i
		print(ans)
for (n, k, data) in q:
	solve(n, k, data)


import io, os

def ri():
	return int(input().strip())

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

def Solve():
	(n, m) = rl()
	a = rl()
	if m <= n:
		tmp = 0
		for i in range(m):
			tmp += a[i]
		ans = tmp
		for i in range(m, n):
			tmp = tmp - a[i - m] + a[i]
			ans = max(ans, tmp)
		print(ans + m * (m - 1) // 2)
	else:
		print(sum(a) + n * m - n * (n + 1) // 2)
T = ri()
while T:
	T -= 1
	Solve()


tc = int(input())
for t in range(tc):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k >= n:
		cun = sum(arr)
		r = n - k
		sm = (k * (k - 1) - r * (r + 1)) // 2
		print(cun + sm)
	else:
		cn = sum(arr[:k])
		mx = cn
		for j in range(k, n):
			cn = cn + arr[j] - arr[j - k]
			if cn > mx:
				mx = cn
		sm = k * (k - 1) // 2
		print(mx + sm)


def read_nums():
	return [int(x) for x in input().split()]

def solve():
	(n, k) = read_nums()
	nums = read_nums()
	if k >= n:
		return sum(nums) + n * (2 * k - n - 1) // 2
	cum_nums = get_cum_sum(nums)
	largest_sum = 0
	for i in range(n - k + 1):
		largest_sum = max(largest_sum, cum_nums[i + k] - cum_nums[i])
	return largest_sum + k * (k - 1) // 2

def get_cum_sum(nums):
	cum_sum = 0
	cum_nums = [0]
	for num in nums:
		cum_sum += num
		cum_nums.append(cum_sum)
	return cum_nums

def main():
	(t,) = read_nums()
	for _ in range(t):
		print(solve())
main()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k < n:
		m = sum(a[:k])
		c = m
		for i in range(k, n):
			c += a[i] - a[i - k]
			m = max(m, c)
		print(m + k * (k - 1) // 2)
	else:
		print(sum(a) + (k - n) * n + n * (n - 1) // 2)


def solve(a, n, k):
	if k > n:
		return sum(a) + n * k - n * (n + 1) // 2
	ksum = k * (k - 1) // 2
	ps = [0] * (n + 1)
	for i in range(n):
		ps[i + 1] = ps[i] + a[i]
	nsum = 0
	for i in range(n - k + 1):
		nsum = max(nsum, ps[i + k] - ps[i])
	return nsum + ksum
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(a, n, k))


t = int(input())
for i in range(0, t):
	(n, k) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	if k > n:
		print(sum(a) + n * k - n * (n + 1) // 2)
	else:
		l = 0
		r = k - 1
		m = sum(a[:k])
		s = m
		for r in range(k, n):
			s = s - a[r - k] + a[r]
			m = max(s, m)
		print(m + k * (k - 1) // 2)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n > k:
		sumi = 0
		for i in range(k):
			sumi += a[i]
		maxi = sumi
		for i in range(k, n):
			sumi += a[i] - a[i - k]
			maxi = max(maxi, sumi)
		print(maxi + k * (k - 1) // 2)
	else:
		print(sum(a) + k * n - n * (n + 1) // 2)


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 1:
		out = a[0] + (k - 1)
	elif k < n:
		maxw = 0
		s = 0
		for i in range(n):
			s += a[i]
			if i >= k:
				s -= a[i - k]
			if i >= k - 1:
				maxw = max(maxw, s)
		out = maxw + (k - 1) * k // 2
	elif k == n:
		out = sum(a) + (k - 1) * k // 2
	else:
		out = sum(a)
		share = k // (n - 1)
		r = k % (n - 1)
		out += (r - 1) * r // 2
		out += (r - 1) * r
		out += (3 * r + n - 3) * (n - r) // 2
		out += (share - 1) * (n - 1) * n
	print(out)
for _ in range(int(input())):
	solve()


def solve(n, k, array):
	ans = 0
	if k <= n:
		ans += int(k * (k - 1) / 2)
		temp = 0
		for i in range(k):
			temp += array[i]
		maxTemp = temp
		for i in range(n - k):
			temp -= array[i]
			temp += array[i + k]
			maxTemp = max(temp, maxTemp)
		ans += maxTemp
	else:
		ans += sum(array)
		temp = n * k
		temp -= int(n * (n + 1) / 2)
		ans += temp
	return ans
t = int(input())
for _ in range(t):
	(n, k) = input().split(' ')
	n = int(n)
	k = int(k)
	array = [int(i) for i in input().split(' ')]
	print(solve(n, k, array))


def resi():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	if k >= n:
		print(n * (k - n) + s + (n - 1) * n // 2)
		return
	tmp = 0
	for i in range(k):
		tmp += a[i]
	maxx = tmp
	for i in range(k, n):
		tmp += a[i]
		tmp -= a[i - k]
		if maxx < tmp:
			maxx = tmp
	print(maxx + k * (k - 1) // 2)
	return
for _ in range(int(input())):
	resi()


x = int(input())

def cal(n, m, arr):
	if m >= n:
		t = sum(arr) + n * (m - 1) - (n - 1) * n // 2
		return t
	t = sum(arr[:m])
	k = t
	for i in range(n - m):
		k -= arr[i]
		k += arr[i + m]
		t = max(t, k)
	return t + m * (m - 1) - m * (m - 1) // 2
for jj in range(x):
	(n, m) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, m, arr))


from itertools import accumulate
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if n == 1:
		print(a[0] + k - 1)
	elif n == 2:
		if k == 1:
			print(max(a))
		else:
			print(sum(a) + k * n - n * (n + 1) // 2)
	elif k == n:
		print(sum(a) + n * (n - 1) // 2)
	elif k < n:
		temp1 = k % n
		preSum = list(accumulate(a, initial=0))
		maxn = 0
		for i in range(n - temp1 + 1):
			maxn = max(maxn, preSum[i + temp1] - preSum[i])
		print(maxn + temp1 * (temp1 - 1) // 2)
	else:
		print(sum(a) + k * n - n * (n + 1) // 2)


def ans(arr, k):
	n = len(arr)
	if k > n:
		s = sum(arr)
		x = n * (n + 1) // 2
		print(s - x + n * k)
	else:
		res = 0
		for i in range(k):
			res += arr[i]
		curr_sum = res
		for i in range(k, n):
			curr_sum += arr[i] - arr[i - k]
			res = max(res, curr_sum)
		print(res + k * (k - 1) // 2)
t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	ans(arr, k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	temp = 0
	if k <= n:
		curr_first = arr[0]
		curr_sum = sum(arr[:k])
		res = curr_sum
		for nn in arr[k:]:
			curr_sum = curr_sum - curr_first + nn
			res = max(res, curr_sum)
			temp += 1
			curr_first = arr[temp]
		print(res + k * (k - 1) // 2)
	else:
		res = sum(arr) + n * (n - 1) // 2 + n * (k - n)
		print(res)


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k >= n:
		print(sum(a) + (k - 1) * n - (n - 1) * n // 2)
		continue
	s = sum(a[:k])
	big = s
	for i in range(k, n):
		s += a[i] - a[i - k]
		big = max(big, s)
	print(big + k * (k - 1) // 2)


t = int(input())
while t:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	if k <= n:
		delta = k * (k - 1) // 2
		tmps = sum(l[:k])
		s = tmps
		for i in range(k, n):
			tmps += l[i]
			tmps -= l[i - k]
			s = tmps if tmps > s else s
	else:
		s = sum(l)
		delta = n * (2 * k - n - 1) // 2
	print(s + delta)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	if n == k:
		print(sum(l) + n * (n - 1) // 2)
	elif n > k:
		m = sum(l[:k])
		c = m
		for i in range(k, n):
			c += l[i] - l[i - k]
			m = max(c, m)
		print(m + k * (k - 1) // 2)
	else:
		sm = 0
		sm = sum(l) + n * (n - 1) // 2
		sm = sm + (k - n) * len(l)
		print(sm)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	if k >= n:
		print(int(sum(nums) + n * (k - 1) - (n - 1) * n / 2))
	else:
		cur_max = sum(nums[0:k])
		current = cur_max
		for j in range(n - k):
			current = current + nums[k + j] - nums[j]
			if current > cur_max:
				cur_max = current
		print(int(cur_max + (k - 1) * k / 2))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	vals = list(map(int, input().split()))
	maxSum = 0
	if k < n:
		workingSum = sum(vals[:k])
		maxSum = workingSum
		for i in range(k, n):
			workingSum += vals[i]
			workingSum -= vals[i - k]
			maxSum = max(maxSum, workingSum)
		timeAdded = k * (k - 1) / 2
	else:
		maxSum = sum(vals)
		maxSum += (k - n) * n
		maxSum += (n - 1) * n / 2
		timeAdded = 0
	print(int(maxSum + timeAdded))


def partial_sum(a, b):
	return (b + a) * (b - a + 1) // 2
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	mushs = list(map(int, input().split()))
	if k >= n:
		print(partial_sum(k - n, k - 1) + sum(mushs))
		continue
	num = sum(mushs[:k])
	M = num
	for i in range(k, n):
		num += mushs[i] - mushs[i - k]
		M = max(M, num)
	print(partial_sum(0, k - 1) + M)


T = int(input())
for testcase in range(T):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	s = sum(a)
	if k >= n:
		print(s + k * n - n * (n + 1) // 2)
	else:
		ps = [0]
		pssum = 0
		for x in a:
			pssum += x
			ps.append(pssum)
		bestsum = 0
		for i in range(n - k + 1):
			if ps[i + k] - ps[i] > bestsum:
				bestsum = ps[i + k] - ps[i]
		print(bestsum + (k - 1) * k // 2)


for time in range(int(input())):
	(n, x) = map(int, input().split())
	nums = [int(a) for a in input().split()]
	if n > x:
		s = 0
		for j in range(x):
			s += nums[j]
		maxi = s
		for j in range(x, n):
			s += nums[j] - nums[j - x]
			maxi = max(s, maxi)
		print(maxi + (x * x - x) // 2)
	else:
		s = sum((j for j in nums))
		print(s + n * (x - 1) - n * (n - 1) // 2)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if k >= n:
		print(sum(a) + n * k - n * (n + 1) // 2)
	else:
		sm = 0
		for i in range(k):
			sm += a[i]
		ans = sm
		for i in range(k, n):
			sm -= a[i - k] - a[i]
			ans = max(ans, sm)
		print(ans + k * (k - 1) // 2)


for h in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	if k >= n:
		a = sum(x)
		b = k // n * n * n - n * (n + 1) // 2
		k = k % n
		c = n * k
		print(a + b + c)
	else:
		for i in range(1, n):
			x[i] += x[i - 1]
		x.append(0)
		m = 0
		for i in range(k - 1, n):
			m = max(m, x[i] - x[i - k])
		print(m + k * (k - 1) // 2)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == 1:
		print(l[0] + k - 1)
	elif k <= n:
		ans = 0
		su = 0
		for i in range(k):
			su += l[i]
		ans = su
		for i in range(k, n):
			su += l[i] - l[i - k]
			ans = max(ans, su)
		print(ans + k * (k - 1) // 2)
	elif k > n:
		print((k - 1) * n + sum(l) - n * (n - 1) // 2)
	t -= 1


n = int(input())
mas = 0
for i in range(n):
	mas = 0
	s = 0
	(x, y) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if y < x:
		mas += sum(l[:y])
		s = mas
		for v in range(y, x):
			s += l[v] - l[v - y]
			mas = max(mas, s)
		mas += y * (y - 1) / 2
	else:
		mas += sum(l) + (len(l) - 1) * (len(l) / 2) + x * (y - x)
	print(int(mas))


runs = int(input())

def solveCaseB(map, x, k):
	return map[x] + (k - 1 + k - x) * x // 2

def solveCaseA(map, x, k):
	max = 0
	for i in range(x + 1):
		if i >= k:
			curr = map[i] - map[i - k]
			if curr > max:
				max = curr
	return max + (1 + k - 1) * (k - 1) // 2
for i in range(runs):
	[x, k] = [int(i) for i in input().split()]
	mapa = [0] + [int(i) for i in input().split()]
	for i in range(1, x + 1):
		mapa[i] += mapa[i - 1]
	if k > x:
		print(solveCaseB(mapa, x, k))
	else:
		print(solveCaseA(mapa, x, k))


read = lambda : map(int, input().strip().split())

def f(a, k):
	if k >= len(a):
		rem = k - len(a)
		base = rem + 1
		ans = a[0] + rem
		for i in a[1:]:
			ans += i + base
			base += 1
		return ans
	else:
		s = sum(a[:k])
		i = 0
		j = k
		ans = s
		while j < len(a):
			s -= a[i]
			s += a[j]
			j += 1
			i += 1
			ans = max(ans, s)
		k -= 1
		ans += k * (k + 1) // 2
		return ans
for _ in range(int(input())):
	(n, k) = read()
	a = list(read())
	print(f(a, k))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	v = list(map(int, input().split(' ')))
	if k >= n:
		ans = int(sum(v) + k * n - n * (n + 1) / 2)
	else:
		s = sum(v[0:k])
		ans = int(s + k * (k - 1) / 2)
		for i in range(1, n - k + 1):
			s -= v[i - 1]
			s += v[i + k - 1]
			ans = max(ans, int(s + k * (k - 1) / 2))
	print(ans)


def solve(a, b, c):
	s = 0
	u = 0
	for i in range(a):
		u += c[i]
		if b <= i:
			u -= c[i - b]
		s = max(s, u)
	return s + (b - 1) * b // 2
for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	if a >= b:
		print(solve(a, b, c))
	else:
		print(solve(a, a, c) + (b - a) * a)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k >= n:
		ans = n * (n + 1) // 2
		ans += (k - 1 - n) * n
		ans += sum(a)
		print(ans)
	else:
		pre = [0] + a.copy()
		for i in range(1, n + 1):
			pre[i] += pre[i - 1]
		ma = 0
		for i in range(0, n + 1 - k):
			su = pre[i + k] - pre[i]
			ma = max(ma, su)
		num = k - 1
		ans = num * (num + 1) // 2
		ans += ma
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	if k >= n:
		print(sum(a) + n * k - n * (n + 1) // 2)
	else:
		window = (((k - 1) % n) ** 2 + (k - 1) % n) / 2
		(l, r, i, ans) = (0, 0, 0, 0)
		while r < n:
			window += a[r]
			if r - l == k:
				window -= a[l]
				l += 1
			r += 1
			ans = max(ans, window)
		print(int(ans))


def ar(n):
	return n * (n - 1) // 2
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k > n:
		ans = sum(a)
		ans += ar(n) + k - n + (k - n) * (n - 1)
	else:
		b = [0]
		s = 0
		for i in a:
			s += i
			b.append(s)
		s = 0
		for i in range(k, n + 1):
			s = max(s, b[i] - b[i - k])
		ans = s
		ans += ar(k)
	print(ans)


t = int(input())
for j in range(t):
	(n, k) = list(map(int, input().split()))
	mushrooms = list(map(int, input().split()))
	sum = [0]
	for i in range(1, n + 1):
		sum.append(mushrooms[i - 1] + sum[i - 1])
	if k > n:
		print(sum[n] + k * n - n * (n + 1) // 2)
	else:
		max_subarray = 0
		for i in range(k, n + 1):
			max_subarray = max(max_subarray, sum[i] - sum[i - k])
		print(max_subarray + k * (k - 1) // 2)


tests = int(input())
for i in range(tests):
	(n, steps) = map(int, input().split())
	florest = [int(n) for n in input().split()]
	if steps <= n:
		sum_ = 0
		for j in range(steps):
			sum_ += florest[j]
		result = sum_
		for j in range(steps, n, 1):
			sum_ += florest[j]
			sum_ -= florest[j - steps]
			result = max(result, sum_)
		result += steps * (steps - 1) / 2
		print(int(result))
	else:
		result = n * (steps - n) + n * (n - 1) / 2
		for j in range(n):
			result += florest[j]
		print(int(result))


t = int(input())
for _ in range(t):
	(a, b) = input().split()
	b = int(b)
	s = list(map(int, input().split()))
	if b < len(s):
		tmp = sum(s[0:b])
		mx = tmp
		for i in range(len(s) - b):
			tmp = tmp - s[i] + s[i + b]
			mx = max(tmp, mx)
		print(mx + b * (b - 1) // 2)
	else:
		l = len(s)
		print(sum(s) + b * l - l * (l + 1) // 2)


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	for i in range(1, n + 1):
		a[i] += a[i - 1]
	if m > n:
		print(a[n] + (m - 1 + m - n) * n // 2)
	else:
		ans = 0
		for i in range(n + 1):
			if i >= m:
				ans = max(ans, a[i] - a[i - m])
		print(ans + (1 + m - 1) * (m - 1) // 2)


testes = int(input())
for t in range(testes):
	(n_forest, tempo) = map(int, input().split())
	mush_pos = [0] + list(map(int, input().split()))
	for i in range(1, n_forest + 1):
		mush_pos[i] += mush_pos[i - 1]
	if tempo > n_forest:
		print(mush_pos[n_forest] + (tempo - 1 + tempo - n_forest) * n_forest // 2)
	else:
		ans = 0
		for i in range(n_forest + 1):
			if i >= tempo:
				ans = max(ans, mush_pos[i] - mush_pos[i - tempo])
		print(ans + (1 + tempo - 1) * (tempo - 1) // 2)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sumArr = [0]
	res = 0
	for i in range(n):
		sumArr.append(sumArr[i] + arr[i])
	if k <= n:
		for i in range(n - k + 1):
			res = max(res, sumArr[i + k] - sumArr[i])
		res += k * (k - 1) / 2
	else:
		res = sumArr[n] + n * (2 * k - n - 1) / 2
	t -= 1
	print(int(res))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().strip().split()]
	a = [int(x) for x in input().strip().split()]
	a = [0] + a
	for i in range(1, len(a)):
		a[i] += a[i - 1]
	if k > n:
		print(a[n] + (k - 1 + k - n) * n // 2)
	else:
		ans = 0
		for i in range(0, 2 * n):
			if i + k <= n:
				ans = max(ans, a[i + k] - a[i])
		print(ans + k * (k - 1) // 2)