#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 = dp[0];
for (int i = 0; i < n - k; i++) {
dp[i + 1] = max({dp[i] + a[i] - b[i + k - 1], dpm[i] + a[i] - pb[i + k] + pb[i]});
dpm[i + k + 1] = max(dpm[i + k], dp[i + 1]);
}
vector<int> maxsuff(n + 1);
for (int i = n - 1; i >= 0; i--) {
maxsuff[i] = max(maxsuff[i], pa[n] - pa[i] - pb[n] + pb[i]);
}
for (int i = 0; i < n - k; i++) {
ans = max(ans, dp[i + 1] + maxsuff[i + k]);
}
return ans;
}
int solvet(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);
int ans = dp[0];
for (int i = 0; i < n; i++) {
dp[i + 1] = max({dp[i] + a[i] - b[i + k - 1], dpm[i] + a[i] - pb[i + k] + pb[i]});
dpm[i + k + 1] = max(dpm[i + k], dp[i + 1]);
}
for (int i = 0; i < n; i++) {
ans = max(ans, dp[i + 1]);
}
return ans;
}
int solve(signed n, signed k, signed *A, signed *B) {
int ans = max(0ll, accumulate(A, A + n, 0ll) - accumulate(B, B + n, 0ll));
ans = max(ans, solves(n, k, A, B, 0));
ans = max(ans, solvet(n, k, A, B, 0));
return ans;
}
