#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int solves(int n, int k, signed *A, signed *B, int shift) {
vector<int> a(2 * n), b(2 * n);
for (int i = 0; i < n; i++) {
a[i] = a[i + n] = A[(i + shift) % n];
b[i] = b[i + n] = B[(i + shift) % n];
}
vector<int> pa(2 * n + 1), pb(2 * n + 1);
for (int i = 0; i < 2 * n; i++) {
pa[i + 1] = pa[i] + a[i];
pb[i + 1] = pb[i] + b[i];
}
vector<int> dp(n + 1, -1e17), dpm(2 * n + 1, -1e17);
dp[0] = -pb[k - 1];
dpm[k] = dp[0];
int ans = 0;
for (int i = 0; i < n; i++) {
dp[i + 1] = max({dp[i] + a[i] - b[i + k - 1], dpm[i] - pb[i + k - 1] + pb[i]});
dpm[i + k + 1] = max(dpm[i + k], dp[i + 1]);
}
return ans;
}
int solve(signed n, signed k, signed *A, signed *B) {
int ans = accumulate(A, A + n, 0ll) - accumulate(B, B + n, 0ll);
for (int i = 0; i < n; i++) {
ans = max(ans, solves(n, k, A, B, i));
}
return ans;
}
