#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define ll long long
const int M = 2e6 + 1;
ll seg[M*2],lz[M*2],dp[M],pre[M*2],b[M*2],a[M],n;
void push(int v,int lc,int rc)
{
seg[lc]+=lz[v],seg[rc]+=lz[v];
lz[lc]+=lz[v],lz[rc]+=lz[v];
lz[v]=0;
}
void modify(int l,int r,ll x,int v=0,int s=0,int e=n)
{
if (l>=e or r<=s)
return;
if (l<=s && e<=r)
{
seg[v]+=x;
lz[v]+=x;
return;
}
int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
push(v,lc,rc);
modify(l,r,x,lc,s,mid);
modify(l,r,x,rc,mid,e);
seg[v]=max(seg[lc],seg[rc]);
}
ll get(int l,int r,int v=0,int s=0,int e=n)
{
if (l>=e or r<=s)
return 0;
if (l<=s && e<=r)
return seg[v];
int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
return max(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}
ll solve1(int l,int r,int k)
{
for (int i=0;i<2*n;i++)
pre[i+1]=pre[i]+b[i];
dp[n-1]=a[n-1]-(pre[n-1+k]-pre[n-1]);
modify(n-1,n,dp[n-1]+pre[n+k-1]-pre[n-1]);
ll ans=0;
for (int i=n-2;i>=l;i--)
{
modify(i+1,min((int)n,i+k+1),b[i+k]);
dp[i]=a[i]+max(0ll,get(0,n))-(pre[i+k]-pre[i]);
modify(i,i+1,dp[i]+pre[i+k]-pre[i]);
}
for(int i=l;i<r;i++)
ans=max(ans,dp[i]);
}
ll solve(int N,int k,int A[],int B[])
{
n=N;
for (int i=0;i<n;i++)
b[i]=b[i+n]=B[i],a[i]=A[i];
ll ans=solve1(k-1,n,k);
for (int i=k-2;i>=0;i--)
{
b[i+n]=0;
ans=max(ans,solve1(i,i+1,k));
}
return ans;
}
