Chef is participating in a pogo stick race. In this competition, there are NN squares (numbered 11 through NN) in a row. Chef must choose a starting square, enter this square and start jumping on his pogo stick. In each jump, if Chef is at a square ss, then he can only jump to the square s+Ks+K. If square s+Ks+K does not exist, Chef jumps out of the row of squares and the race ends for him. It is not allowed to stop jumping any earlier.
Each square has a value; let’s denote the value of the ii-th square by AiAi. Initially, Chef has 00 points. When he jumps in some square (including the initial square), he is awarded a number of points equal to the value of this square, exactly once. Note that if this value is negative, the number of Chef’s points is decreased.
Determine the maximum possible total number of points Chef can get if he selects the initial cell optimally.
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains two space-separated integers NN and KK.
- The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
For each test case, print a single line containing one integer ― the maximum number of points.
- |Ai|≤10,000|Ai|≤10,000 for each valid ii
- the sum of NN over all test cases does not exceed 106106
Subtask #1 (30 points):
- the sum of NN over all test cases does not exceed 10,00010,000
Subtask #2 (70 points): original constraints
2 5 2 3 6 4 7 2 5 3 3 -5 6 3 10
this is my code at the submission time i am getting wrong.