409880: GYM103821 L ResliPhobia
Description
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.
InputEach 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$$$.
OutputFor each test case, print a single line containing the maximum number of balls in the chosen sub-sequence.
ExampleInput4 2 1 2 3 4 1 10 10 11 11 5 2 10 100 98 101 3 5 1 1 1 1 1 1Output
5 21 302 1Note
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$$$$$$.$$$