#include"homecoming.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using lint = long long;
lint solve(int N, int K, int *A, int *B){
int n=N,k=K;
lint a[n],b[2*n];
for(int i=0;i<n;i++)
a[i]=A[i],b[i]=B[i];
lint ans=0;
{
for(int i=n;i<2*n;i++)b[i]=0;
lint pref[2*n];
for(int i=0;i<2*n;i++)pref[i]=b[i]+(i?pref[i-1]:0);
auto p=[&](int l,int r)->lint {
if(l)return pref[r]-pref[l-1];
return pref[r];
};
lint dp[n][2];
dp[0][0]=dp[0][1]=a[0]-p(0,k-1);
for(int i=1;i<n;i++){
dp[i][0]=max(dp[i-1][0]-b[i+k-1],dp[i-1][1]-p(i,i+k-1))+a[i];
dp[i][1]=max(dp[i-1][1],dp[i][0]);
}
ans=max(ans,dp[n-1][1]);
}
{
for(int i=n;i<2*n;i++)b[i]=b[i-n];
lint pref[2*n];
for(int i=0;i<2*n;i++)pref[i]=b[i]+(i?pref[i-1]:0);
auto p=[&](int l,int r)->lint {
if(l)return pref[r]-pref[l-1];
return pref[r];
};
lint dp[n][2];
dp[0][0]=a[0]-p(0,k-1);
dp[0][1]=max(dp[0][0],0ll);
for(int i=1;i<n;i++){
dp[i][0]=max(dp[i-1][0]-b[i+k-1],dp[i-1][1]-p(i,i+k-1))+a[i];
dp[i][1]=max(dp[i-1][1],dp[i][0]);
}
ans=max(ans,dp[n-1][1]);
}
return ans;
}
