#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
long long a,s,d[2000002][2],f[2000002][2],g[2000002],h[2000002],j,k,l,i,n,m;
long long get(int l,int r){
l++;r++;
//cout<<l<<" "<<r<<" "<<g[l]<<" "<<g[r-1]<<" "<<g[n]<<endl;
if(r>=l) return g[r]-g[l-1];
else return (g[n]-g[l-1])+g[r];
}
int gi(int i){
if(i>=n) i-=n;
return i;
}
long long solve(int N,int K,int *A,int *B){
long long s1=A[0]-B[0];
n=N;
k=K;
g[1]=B[0];
g[0]=0;
for(i=2;i<=n;i++){
s1+=A[i-1]-B[i-1];
g[i]=g[i-1]+B[i-1];
}
if(n==k) return max(s1,0ll);
//memset(d,~0,sizeof d);
d[0][1]=-1000000000000000000ll;
d[0][0]=A[0]-g[k];
h[n-1]=A[n-1];//cout<<d[0][0]<<" "<<d[0][1]<<endl;
for(i=n-2;i>=n-k;i--) h[i]=h[i+1]+A[i];
d[n-1][0]=0;
for(i=1;i<n;i++){
if(i+k-1>=n-1) {
if(i==n-1) d[i][0]=max(d[i][0],d[i-1][0]+A[i]-((i+k==n)*B[n-1])); else
d[i][0]=d[i-1][0]+A[i]-((i+k==n)*B[n-1]);
if(d[i-1][1]+A[i]-get(i,n-1)>d[i][0]){
d[i][0]=d[i-1][1]+A[i]-get(i,n-1);
}
//d[n-1][0]=max(d[n-1][0],max(d[i-k-1][0],d[i-k-1][1])+h[i]-get(i,n-1));
d[i][1]=max(d[i-1][1],d[i-1][0]);
//cout<<d[i][0]<<" "<<d[i][1]<<endl;
continue;
}
d[i][0]=d[i-1][0]+A[i]-B[gi(i+k-1)];
if(d[i-1][1]!=-1 && d[i-1][1]+A[i]-get(i,gi(i+k-1))>d[i][0]) {
d[i][0]=d[i-1][1]+A[i]-get(i,gi(i+k-1));
}
d[i][1]=max(d[i-1][1],d[i-1][0]);
}
f[0][0]=-1000000000000000000ll;
f[0][1]=0;
for(i=1;i<n;i++){
f[i][0]=f[i-1][0]+A[i]-B[gi(i+k-1)];
//cout<<i<<"* "<<-get(i,gi(i+k-1))<<endl;
if(f[i-1][1]+A[i]-get(i,gi(i+k-1))>f[i][0]) {
f[i][0]=f[i-1][1]+A[i]-get(i,gi(i+k-1));
}
f[i][1]=max(f[i-1][1],f[i-1][0]);//cout<<f[i][0]<<" "<<f[i][1]<<endl;
}
return (long long)(max(max(d[n-1][0],d[n-1][1]),max(f[n-1][0],f[n-1][1])));
}
