import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
for t in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [-float("inf")]*(2*n + 2)
dp[0] = 0
for _ in range(k):
dp2 = [-float("inf")]*(2*n + 2)
for i in range(_, n):
#ends at index, doesnt end at index
p, q = 2*i + 2, 2*i + 3
dp2[p] = max(dp[p-2] + a[i], dp2[p-2] + a[i], dp2[p-1] + a[i])
dp2[q] = max(dp2[p], dp2[p-2], dp[p-1] + a[i], dp[p-2] + a[i], dp2[p-1])
dp = list(dp2)
print(dp[-1])
Comments
0 B
|👍
/👎