#include <bits/stdc++.h>
#include "homecoming.h"
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
long long solve(int N, int K, int *A, int *B){
vector<ll> pre(2*N);
for(ll i = 0; i < 2*N; ++i){
pre[i] = B[i%N];
if(i)
pre[i] += pre[i-1];
}
vector<vector<ll>> dp(N, vector<ll>(2, -1e18));
ll ans = 0;
dp[0][1] = A[0]-pre[K-1];
for(int i = 1; i < N; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0]+A[i]-pre[min(i+K-1, N-1)]+pre[i-1];
if(i+K-1 < N)
dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]-B[i+K-1]);
else
dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]);
dp[i][1] = max((ll)-1e18, dp[i][1]);
}
ans = max({ans, dp[N-1][0], dp[N-1][1]});
dp = vector<vector<ll>>(N, vector<ll>(2, -1e18));
dp[0][0] = 0;
for(int i = 1; i < N; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0]+A[i]-pre[i+K-1]+pre[i-1];
dp[i][1] = max(dp[i][1], dp[i-1][1]+A[i]-B[(i+K-1)%N]);
dp[i][1] = max((ll)-1e18, dp[i][1]);
}
ans = max({ans, dp[N-1][0], dp[N-1][1]});
return ans;
}
