You are given an array $a$ of length $n$. A subsequence of this array is valid, if it satisfies these two conditions:
- There shouldn't be any two even numbers within a distance of $K$, both which have been chosen in the subsequence. i.e. there shouldn't be two indices $i, j$ such that $a_i$ and $a_j$ are even, $|i - j| \leq K$ and $a_i$ and $a_j$ are in the subsequence. 
- Similarly, there shouldn't be any two odd numbers within a distance of $K$, both which have been chosen in the subsequence
The sum of a subsequence is the sum of all the numbers in it. Your task is find the maximum sum possible in a valid subsequence of the given array. Print this maximum sum.

-----Input-----
- The first line of the input contains an integer $T$ denoting the number of test cases. The description of the test cases follows.
- The first line of each test case contains two space-separated integers $n, k$.
- The second line of each test case contains $n$ space-separated integers denoting the array $a$.

-----Output-----
For each test case, output an integer corresponding to the answer of the problem.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le n \leq 10^5$
- $1 \le k \leq  n$
- $1 \le a_i \leq 10^9$
- Sum of $n$ over all the test cases doesn't exceed $10^6$

-----Example Input-----
3
1 1
3
2 1
2 2
5 2
1 2 3 4 6

-----Example Output-----
3
2
11

-----Explanation:-----
Testcase 2: Only one of the two 2s can be chosen. Hence the answer is 2.
Testcase 3: The subsequence containing the second, third and fifth numbers is a valid subsequence, and its sum is 2+3+6 = 11. You can check that this is the maximum possible, and hence is the answer.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
import math

def main(arr, k):
	x = []
	y = []
	for e in arr:
		if e % 2 == 0:
			x.append(e)
			y.append(0)
		else:
			x.append(0)
			y.append(e)
	a = [0] * n
	b = [0] * n
	a[0] = x[0]
	b[0] = y[0]
	for i in range(1, n):
		if i < k:
			a[i] = max(x[i], a[i - 1])
			b[i] = max(y[i], b[i - 1])
		else:
			a[i] = max(x[i] + a[i - k - 1], a[i - 1])
			b[i] = max(y[i] + b[i - k - 1], b[i - 1])
	print(a[-1] + b[-1])
	return
for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	main(arr, k)


def solve(array, k, n):
	even = []
	odd = []
	for i in range(n):
		if array[i] % 2 == 0:
			even.append(array[i])
			odd.append(0)
		else:
			odd.append(array[i])
			even.append(0)
	dpEven = [0] * n
	dpOdd = [0] * n
	dpEven[0] = even[0]
	dpOdd[0] = odd[0]
	i = 1
	while i <= k and i < n:
		dpEven[i] = max(dpEven[i - 1], even[i])
		dpOdd[i] = max(dpOdd[i - 1], odd[i])
		i += 1
	for i in range(k + 1, n):
		dpEven[i] = max(dpEven[i - 1], dpEven[i - k - 1] + even[i])
	for i in range(k + 1, n):
		dpOdd[i] = max(dpOdd[i - 1], dpOdd[i - k - 1] + odd[i])
	return dpOdd[-1] + dpEven[-1]
queries = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	queries.append((list(map(int, input().split())), k))
for query in queries:
	print(solve(query[0], query[1], len(query[0])))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().strip().split()))
	ar = list(map(int, input().strip().split()))
	even = []
	odd = []
	for i in range(n):
		if ar[i] % 2 == 0:
			even.append(ar[i])
			odd.append(0)
		else:
			even.append(0)
			odd.append(ar[i])
	dp1 = [0] * n
	dp2 = [0] * n
	dp1[0] = even[0]
	dp2[0] = odd[0]
	for i in range(1, n):
		if i < k + 1:
			dp1[i] = max(dp1[i - 1], even[i])
		else:
			dp1[i] = max(dp1[i - 1], dp1[i - k - 1] + even[i])
	for i in range(1, n):
		if i < k + 1:
			dp2[i] = max(dp2[i - 1], odd[i])
		else:
			dp2[i] = max(dp2[i - 1], dp2[i - k - 1] + odd[i])
	print(dp1[-1] + dp2[-1])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dpo = [0] * n
	dpe = [0] * n
	for (i, a) in enumerate(arr):
		if i > k:
			if a & 1:
				dpo[i] = max(dpo[i - 1], dpo[i - k - 1] + a)
				dpe[i] = dpe[i - 1]
			else:
				dpe[i] = max(dpe[i - 1], dpe[i - k - 1] + a)
				dpo[i] = dpo[i - 1]
		elif a & 1:
			dpo[i] = max(dpo[i - 1], a)
			dpe[i] = dpe[i - 1]
		else:
			dpe[i] = max(dpe[i - 1], a)
			dpo[i] = dpo[i - 1]
	print(dpo[-1] + dpe[-1])


def sol(b, k):
	l = len(b)
	if l == 0:
		return 0
	elif l == 1:
		return A[b[0]]
	n = b[-1]
	dp = [0] * (n + 1)
	dp[n] = A[n]
	x = 2
	ret = 0
	for i in range(n - 1, -1, -1):
		if i > b[l - x]:
			dp[i] = dp[i + 1]
		elif i < b[0]:
			ret = dp[i + 1]
			break
		else:
			if i + k + 1 > n:
				dp[i] = max(A[i], dp[i + 1])
			else:
				dp[i] = max(A[i] + dp[i + k + 1], dp[i + 1])
			x += 1
	if ret:
		return ret
	return dp[0]
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	(odd, even) = ([], [])
	for i in range(len(A)):
		if A[i] % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	ans = sol(odd, k) + sol(even, k)
	print(ans)


T = int(input())
while T > 0:
	(N, K) = list(map(int, input().split()))
	A = [int(e) for e in input().split()]
	E = [0] * N
	LE = -1
	LO = -1
	O = [0] * N
	if A[0] % 2 == 0:
		E[0] = A[0]
		LE = 0
	else:
		O[0] = A[0]
		LO = 0
	i = 1
	while i < N:
		if A[i] % 2 == 0:
			O[i] = O[i - 1]
			if LE != -1:
				if abs(i - LE) <= K:
					if i - K - 1 >= 0:
						ADDI = E[i - K - 1]
					else:
						ADDI = 0
					if E[LE] >= A[i] + ADDI:
						E[i] = E[LE]
						LE = LE
					else:
						E[i] = A[i] + ADDI
						LE = i
				else:
					E[i] = E[LE] + A[i]
					LE = i
			else:
				E[i] = E[i - 1] + A[i]
				LE = i
		else:
			E[i] = E[i - 1]
			if LO != -1:
				if abs(i - LO) <= K:
					if i - K - 1 >= 0:
						ADDI = O[i - K - 1]
					else:
						ADDI = 0
					if O[LO] >= A[i] + ADDI:
						O[i] = O[LO]
						LO = LO
					else:
						O[i] = A[i] + ADDI
						LO = i
				else:
					O[i] = O[LO] + A[i]
					LO = i
			else:
				O[i] = O[i - 1] + A[i]
				LO = i
		i = i + 1
	print(E[N - 1] + O[N - 1])
	T = T - 1


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

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

def li():
	return list(mi())
from collections import deque
for t in range(ii()):
	(n, k) = mi()
	a = [0] + li()

	def solve(a, k):
		n = len(a)
		dp = [0] * n
		d = deque()
		d.append((0, 0))
		for i in range(1, n):
			if i - d[0][0] > k:
				d.popleft()
			dp[i] = max(d[0][1], a[i] + (dp[i - k - 1] if i >= k + 1 else 0))
			while d and d[-1][1] <= dp[i]:
				d.pop()
			d.append((i, dp[i]))
		return d[0][1]
	odd = solve([x if x % 2 else 0 for x in a], k)
	even = solve([0 if x % 2 else x for x in a], k)
	print(odd + even)