#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
const ll INF = 1e18;
struct mat {
ll a, b, c, d;
};
mat mul(const mat &a, const mat &b) {
mat c;
c.a = max(a.a + b.a, a.b + b.c);
c.b = max(a.a + b.b, a.b + b.d);
c.c = max(a.c + b.a, a.d + b.c);
c.d = max(a.c + b.b, a.d + b.d);
return c;
}
ll solve(int N, int K, int *A, int *B) {
ll ret = 0;
forn(i, N) ret += A[i] - B[i];
ll window = 0;
forn(i, K) window += B[i];
vector<mat> val(N);
forn(i, N) {
val[i] = {0, -window + A[i % N], 0, -B[(i + K - 1) % N] + A[i % N]};
window -= B[i % N];
window += B[(i + K) % N];
}
vector<mat> pref(N + 1), suff(N + 1);
pref[0] = suff[N] = {0, -INF, -INF, 0};
forn(i, N) pref[i + 1] = mul(pref[i], val[i]);
dforn(i, N) suff[i] = mul(val[i], suff[i + 1]);
forn(i, N + 1) {
mat curr = mul(suff[i], pref[i]);
ret = max({ret, curr.a, curr.b});
}
return ret;
}
