#include <stdio.h>#include <stdlib.h>int main(){ int F[ 4 ][ 50005 ]; int T,N,M,t,i,m,l,r,s; while ( ~scanf("%d",&T) ) for ( t = 1 ; t <= T ; ++ t ) { scanf("%d",&N); for ( i = 1 ; i <= N ; ++ i ) scanf("%d",&F[ 0 ][ i ]); scanf("%d",&M); for ( s = 0,l = i = 1 ; i <= N ; ++ i ) { s += F[ 0 ][ i ]; if ( i-l >= M ) s -= F[ 0 ][ l ++ ]; F[ 1 ][ i ] = s; } for ( m = 2 ; m <= 3 ; ++ m ) for ( s = 0,i = 1 ; i <= N ; ++ i ) { if ( s < F[ m-1 ][ i-M ] ) s = F[ m-1 ][ i-M ]; F[ m ][ i ] = s + F[ 1 ][ i ]; } int max = 0; for ( i = 1 ; i <= N ; ++ i ) if ( max < F[ 3 ][ i ] ) max = F[ 3 ][ i ]; printf("%dn",max); } return 0;}
