#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+7; int n,k; int a[N]; //O(T2^n) Brute force #define lb(x) ((x)&(-(x))) #define ctz(x) __builtin_ctzll(x) vector<int> E[N]; int Sum[N]; bool vis[N]; inline void Init_BF(){ int U=(1<<n)-1; for(int S=1;S<=U;S++)Sum[S]=Sum[S^lb(S)]+a[ctz(lb(S))+1]; for(int S=0;S<=U;S++)E[S].clear(); for(int S=0;S<=U;S++){ vis[S]=0; int t=(1<<k)-1; for(int j=0;j<=n-k;j++){ int S1=S|t; int S2=S&(U-t); E[S].push_back(S1); E[S].push_back(S2); t<<=1; } } } inline void DFS(int u){ if(vis[u])return; vis[u]=1; for(auto v:E[u])DFS(v); } inline void slv_BF(){ Init_BF(); DFS(0); int Ans=0; for(int S=0;S<=(1<<n)-1;S++)if(vis[S])Ans=max(Ans,Sum[S]); cout<<Ans<<endl; } //O(Tn) std? int Pre0[N]; int Pre[N]; inline void slv_STD(){ for(int i=1;i<=n;i++)Pre[i]=Pre[i-1]+a[i],Pre0[i]=Pre0[i-1]+(a[i]>=0)*a[i]; int Ans=0; for(int i=1;i<=n-k+1;i++){ Ans=max(Ans,Pre0[i-1]+Pre0[n]-Pre0[i+k-1]+max(Pre[i+k-1]-Pre[i-1],0ll)); }cout<<Ans<<endl; } signed main(){ #ifndef ONLINE_JUDGE freopen("color.in","r",stdin); freopen("color.out","w",stdout); #endif int T; cin>>T; while(T--){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; if(n<=13)slv_BF(); else slv_STD(); }return 0; }