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.

Difficulty: interview

Starter code:

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))



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))



'''
    ssisodia507@gmail.com
'''


def solve(array,k,n):
 
 # storing even and odd values
 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 will store the maximum sum of even elements till index i-th
 # and dpOdd of odd elements till index i-th
 dpEven=[0]*n
 dpOdd=[0]*n
 dpEven[0]=even[0]
 dpOdd[0]=odd[0]
 
 # from index 0 to k we can only select one even value and one odd value
 # so store the maximum even value till index k and maximum odd value 
 # till index k
 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
 
 # now for any element we have two choices
 # either choose it or leave it.
 
 # we will consider the case which will give maximum sum
 # so we will find the sum after leaving the element(which is previous
 # maximum sum ) and after choosing the element(previous sum+currentvalue) 
 # and pick the one which give maximum sum
 
 # we will handle even and odd cases separately 
 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])))

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])))

# cook your dish here
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])

# cook your dish here
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])

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]
  else:
   if 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)
 # print(*dpe)
 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)

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)

for _ in range(int(input())):
 n,k = list(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]
  else:
   if 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)
 # print(*dpe)
 print(dpo[-1]+dpe[-1])


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
  #print(E,O,E[N-1]+O[N-1])
  
  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)