题目描述
On a planet called Natoon, a person's wealth as well as health is measured by the amount of gold the person has. For example if a person has 2kg of gold then he will leave 2 more days [2kg=2000gm=2days]. The gold can be borrowed/lend from/to other persons or gold banks. The person in need of your help is Mr. Jabba.
Mr. Jabba is running out of gold and hence his death is coming nearer. Mr. Jabba needs your help to live longer.
A very wealthily person decides to give away free gold worth 1000 years.
The person releases N slips, A[1],A[2],…..A[N]. Each slip has a gold-amount(can be both +ve and -ve).
A person can pick any number of slips(even none, or all of them, or some of them) out of the N slips.
But the rich person has a restriction, he announced one more number K. Restriction is that, if a person picks a slip A[i], then the next slip that he can choose to pick will me A[i+K+1]. It means there should be a difference of at least K between the indices of the slips picked.
Now slips should be picked in such a way that their sum results in maximum positive time-amount possible with given restriction.
If you predict the maximum positive sum possible, then you win.
Help our Jabba the Hutt in order to live longer!
Input:::
First line of the test file contains single number T, the number of test cases to follow.
Each test case consists of two lines.
First line contains two numbers N and K , separated by a space. Second line contains the N numbers A[1], A[2] ..... A[N] separated by space.
Output:::
For every test case, output in a single line the maximum positive sum possible, that is output for the case.
Constraints:
T ≤ 250,
N ≤ 10000,
-109 ≤ A[i] ≤ 109,
0 ≤ K ≤ N-1
SAMPLE INPUT
2
10 1
1 2 -3 -5 4 6 -3 2 -1 2
10 2
1 2 -3 -5 4 6 -3 2 -1 2
SAMPLE OUTPUT
12
10
Explanation
1st Case: We can take slips { A[2]=2, A[6]=6, A[8]=2, A[10]=2 }, slips are atleast 1 indices apart this makes maximum sum, A[2]+A[6]+A[8]+A[10]=12
2nd Case: We can take slips { A[2]=2, A[6]=6, A[10]=2 }, slips are atleast 2 indices apart this makes maximum sum, A[2]+A[6]+A[10]=10
输入格式
见题面
输出格式
见题面