#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define INF 2e18
#define MOD 1e9+7
long long solve(int N, int K, int *A, int *B){
ll n=N, k=K;
vector<ll> a(n+1), b(2*n+1), pref(2*n+1);
vector<vector<ll>> dp(n+1, vector<ll>(2));
for (ll i=1; i<=n; i++) a[i]=A[i-1];
for (ll i=1; i<=n; i++) {b[i]=B[i-1]; pref[i]=pref[i-1]+b[i];}
for (ll i=n+1; i<=2*n; i++) pref[i]=pref[i-1];
ll res; res=dp[1][0] = dp[1][1] = a[1]-pref[k];
for (ll i=2; i<=n; i++){
dp[i][1]=max(dp[i-1][1]-b[i+k-1], dp[i-1][0]-pref[i+k-1]+pref[i-1])+a[i];
dp[i][0]=max(dp[i-1][1], dp[i-1][0]);
}
res=max({res, dp[n][0], dp[n][1]});
for (ll i=n+1; i<=2*n; i++) {b[i] = b[i-n]; pref[i]=pref[i-1]+b[i];}
dp[1][0] = 0;
dp[1][1] = a[1]-pref[k];
for (ll i=2; i<=n; i++){
dp[i][1]=max(dp[i-1][1]-b[i+k-1], dp[i-1][0]-pref[i+k-1]+pref[i-1])+a[i];
dp[i][0]=max(dp[i-1][1], dp[i-1][0]);
}
res=max({res, dp[n][1], dp[n][0]});
return res;
}
