409880: GYM103821 L ResliPhobia

Coach Mohammed Resli (A.K.A EleCursity), has a strange phobia, called ResliPhobia. It's a condition when someone has a fear of consecutive numbers having the same parity. A degree $$$K$$$ of this phobia is when you see $$$\bf{strictly}$$$ more than $$$K$$$ consecutive even OR odd numbers.

Coach Tareq is aware of Resli's condition, that's why he wants to help him. Tareq has $$$N$$$ bags, each bag contains $$$A_i$$$ balls. He wants to choose a sub-sequence of these bags, such that this sub-sequence has the most number of balls, and it won't make coach Resli afraid, can you help Tareq find the maximum number of balls in the chosen sub-sequence?

Note that a sub-sequence of an array $$$A$$$ is defined as a sequence that can be obtained from $$$A$$$ by deleting some elements (possibly none), without changing the order of the remaining elements.

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$N$$$ ($$$1\le N \le 1000$$$) and $$$K$$$ ($$$1 \le K \le N$$$) — Number of bags and the phobia degree.

The second line of each test case contains $$$N$$$ numbers $$$A_1$$$, $$$A_2$$$, $$$...$$$, $$$A_n$$$ ($$$1\le A_i \le 1000$$$) — Number of balls in each bag.

It is $$$\bf{guaranteed}$$$ that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.

For each test case, print a single line containing the maximum number of balls in the chosen sub-sequence.

4
2 1
2 3
4 1
10 10 11 11
5 2
10 100 98 101 3
5 1
1 1 1 1 1

5
21
302
1

In the first test case, we can take the whole array as a subsequence, so the corresponding sum will be $$$2$$$ $$$+$$$ $$$3$$$ $$$=$$$ $$$5$$$$$$.$$$

In the second test case, it is optimal to take $$$[$$$$$$10$$$, $$$11$$$$$$]$$$ as a subsequence because since ($$$k$$$ $$$=$$$ $$$1$$$) we can't take two even elements in a row and we can't take two odd elements in a row, so the answer will be $$$10$$$ $$$+$$$ $$$11$$$ $$$=$$$ $$$21$$$$$$.$$$