Reign

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The Baratheons have been ruling in the Seven Kingdoms for many years. They have seen a lot: prosperity and hunger, tranquility and rebellions, live and death. But nevertheless, they still hold the throne.
King Joffrey Baratheon's reign is running now. As a wise man, he honors the history of his family. So, he commanded to build up two monuments, that will remind about some historical periods of the Baratheons.
Formally, the Baratheons have been ruling for N years. Every year is described by an integer A_{i}, the level of prosperity in ith year. If ith year was a great year, then A_{i} might be a positive integer. Otherwise, if ith year was a horrible year, then A_{i} might be a negative integer.
Each historical period can be described as two integers S and F, the start and the finish of the period respectively. Of course, S is not greater than F for each period, that we consider in this task.
You are to pick two historical periods, but there are some rules:
 Two periods shouldn't have common years. I.e. a period [1, 5] has no common years with a period [6, 7];
 The first period should start earlier than the second one. I.e. a period [1, 5] starts earlier than [6, 7];
 Two periods shouldn't be too close to each other. There must be at least K years between the finish of the first period and the start of the second period. I.e. periods [1, 5] and [10, 10] can be chosen in case K equals to 4, while they can't in case K equals to 5.
 The sum of the levels of prosperity in chosen years should be as big as possible.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.The first line of each test case contains two integers N and K denoting the length of the Baratheons' reign and the minimal amount of years between two chosen periods.
The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N} denoting the levels of prosperity in corresponding years.
Output
For each test case, output a single line containing the required integer.
Constraints
 1 ≤ T ≤ 5;
 2 ≤ N ≤ 10^{5};
 0 ≤ K ≤ 10^{5};
 10^{9} ≤ A_{i} ≤ 10^{9} for every 1 ≤ i ≤ N;
 K + 2 ≤ N
Example
Input: 3 5 3 1 1 2 3 1 8 3 5 5 1 2 3 1 2 2 6 0 5 1 5 0 1 9 Output: 2 12 18
Explanation
There are T = 3 test cases the input.
The first test case: N equals to 5, K equals to 3, A[] equals to {1, 1, 2, 3, 1}. There is the only option: we have to choose [1, 1] and [5, 5] periods.
The second test case: N equals to 8, K equals to 3, A[] equals to {5, 5, 1, 2, 3, 1, 2, 2}. It is optimal to choose [1, 2] and [7, 7] periods. That is the only optimal choice that you can make.
The second test case: N equals to 6, K equals to 0, A[] equals to {5, 1, 5, 0, 1, 9}. It is optimal to choose [1, 3] and [6, 6] periods. But that is not the only optimal choice that you can make.
Author:  kostya_by 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/REIGN 
Tags  dec13, easy, kostya_by 
Date Added:  6112013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions