#include <bits/stdc++.h>
#include "homecoming.h"
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;
int solve(signed n, signed k, signed x[], signed y[]) {
// put into vectors
int res = 0;
vector<int> a(2 * n), b(2 * n), bpref(2 * n);
for(int i = 0; i < n; i++) {
a[i] = x[i], b[i] = y[i];
bpref[i] = (i ? bpref[i - 1] : 0) + b[i];
res += a[i] - b[i];
}
for(int i = n; i < 2 * n; i++) {
a[i] = a[i - n], b[i] = b[i - n];
bpref[i] = bpref[i - 1] + b[i];
}
// dp setup
vector<vector<int>> dp(n + 1, vector<int>(2, LONG_MIN));
// first case
// bug when tries to take everything, but doesn't matter since always worse than res above
dp[0][1] = 0;
for(int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(dp[i - 1][1] + a[i - 1] - b[i + k - 2], dp[i - 1][0] + a[i - 1] - bpref[i + k - 2] - (i > 1 ? bpref[i - 2] : 0));
}
res = max(res, dp[n][1]);
// second case
int end;
for(int x = 1; x <= k + 1; x++) {
for(int i = 0; i <= n; i++) dp[i] = {LONG_MIN, LONG_MIN};
dp[x - 1] = {0, LONG_MIN}, end = n + x - k - 1;
for(int i = x; i <= end; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(dp[i - 1][1] + a[i - 1] - b[i + k - 2], dp[i - 1][0] + a[i - 1] - bpref[i + k - 2] - (i > 1 ? bpref[i - 2] : 0));
}
res = max(res, max(dp[end][0], dp[end][1]));
}
return res;
}
