Even Odd subsequences

All submissions for this problem are available.
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 spaceseparated integers $n, k$.  The second line of each test case contains $n$ spaceseparated 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.Author:  admin2 
Tags  admin2 
Date Added:  17122018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, kotlin 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions