#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
typedef long long ll;
ll pre[4000001];
long long int solve(int N, int K, int *A, int *B){
ll ans = 0LL;
for(int z = 0; z<=K; z++){
ll here = 0LL;
for(int i = 0; i<z; i++){
here -= B[i];
}
pre[0] = 0LL;
for(int i = 1; i<=N; i++){
if(i<=z){
pre[i] = 0LL;
pre[i+N] = 0LL;
}
else{
pre[i] = B[i-1];
pre[i+N] = B[i-1];
}
}
for(int i = 1; i<=2*N; i++){
pre[i] += pre[i-1];
}
ll f[N];
//choosing to buy whole thing
ll g[N];
//choosing to add last one
//[i,i+K-1]
for(int i = N-1; i>=0; i--){
f[i] = 0;
g[i] = 0;
//F
ll takeF = pre[i+K] - pre[i];
takeF = -takeF;
takeF += A[i];
if(i<N-1){
takeF += g[i+1];
}
f[i] = max(f[i],takeF);
if(i<N-1){
f[i] = max(f[i],f[i+1]);
}
//G
int aft = i+K-1;
int ind = aft;
if(ind>=N){
ind -= N;
}
//take it
ll takeG = A[i];
if(ind>=z){
takeG -= B[ind];
}
if(i<N-1){
takeG += g[i+1];
}
g[i] = max(takeG,g[i]);
if(aft+1<N){
g[i] = max(g[i],f[aft+1]);
}
}
here += f[0];
ans = max(ans,here);
}
return ans;
}
