//

Problem 2013 A short problem

/*

Accept: 158 Submit: 452

Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

The description of this problem is very short. Now give you a string(length N), and ask you the max sum of the substring which the length can't small than M.

Input

The first line is one integer T(T≤20) indicates the number of the test cases. Then for every case, the first line is two integer N(1≤N≤1000000) and M(1≤M≤N).

Then one line contains N integer indicate the number. All the number is between -10000 and 10000.

Output

Output one line with an integer.

Sample Input

2

5 1

1 -2 -2 -2 1

5 2

1 -2 -2 -2 1

Sample Output

1

-1

*/

#include

"

iostream

"

using

namespace

std;

const

int

M

=

1000005

;

int

t,n,m;

int

i,j;

int

a[M];

int

sum[M];

int

f[M];

int

cmp(

int

a,

int

b)

{

return

a

>

b

?

a:b;

}

int

main()

{

scanf(

"

%d

"

,

&

t);

while

(t

--

)

{

scanf(

"

%d %d

"

,

&

n,

&

m);

for

(i

=

1

;i

<=

n;i

++

) scanf(

"

%d

"

,

&

a[i]);

int

i,Max

=-

0x7fffffff

;

sum[

0

]

=

0

;

for

(i

=

1

;i

<=

n;i

++

) sum[i]

=

sum[i

-

1

]

+

a[i];

f[m

-

1

]

=

sum[m

-

1

];

for

(i

=

m; i

<=

n; i

++

)

{

f[i]

=

cmp( f[i

-

1

]

+

a[i], sum[i]

-

sum[i

-

m]);

if

(f[i]

>

Max) Max

=

f[i];

}

printf(

"

%d\n

"

,Max);

}

return

0

;

}