#include "homecoming.h"
#include <iostream>
using namespace std;
using ll = long long;
const int MAXN = 2000000;
ll INF = 10000000000000000LL;
struct DpVector
{
ll a, b;
static const DpVector id;
};
const DpVector DpVector::id = {0, -INF};
struct DpMatrix
{
ll a, b, c, d;
/// f({x, y}) = {max(x+a, y+b), max(x+c, y+d)}
/// ( a b )
/// ( c d )
static const DpMatrix id;
static void mult(const DpMatrix &a, const DpMatrix &b, DpMatrix &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);
}
static void mult(const DpMatrix &a, const DpVector &b, DpVector &c)
{
c.a = max(a.a + b.a, a.b + b.b);
c.b = max(a.c + b.a, a.d + b.b);
}
};
const DpMatrix DpMatrix::id = {0, -INF, -INF, 0};
int n, k;
int *a, *b;
ll sb[MAXN+2];
DpMatrix pref[MAXN+2], suf[MAXN+2], auxmat;
DpVector auxvec[2];
void calcSb()
{
sb[0] = 0;
for (int i = 0; i < k; i++) {
sb[0] += b[i];
}
for (int i = 1; i < n; i++) {
sb[i] = sb[i-1] - b[i-1] + b[(i+k-1)%n];
}
}
void calcPrefMats()
{
pref[0] = {0, 0, a[0]-sb[0], a[0]-b[k-1]};
for (int i = 1; i < n; i++) {
auxmat.c = a[i] - sb[i];
auxmat.d = a[i] - b[(i+k-1)%n];
DpMatrix::mult(auxmat, pref[i-1], pref[i]);
}
}
void calcSufMats()
{
suf[n-1] = {0, 0, a[n-1]-sb[n-1], a[n-1]-b[(n+k-2)%n]};
for (int i = n-2; i >= 0; i--) {
auxmat.c = a[i] - sb[i];
auxmat.d = a[i] - b[(i+k-1)%n];
DpMatrix::mult(suf[i+1], auxmat, suf[i]);
}
}
long long getSimpleAns()
{
long long ans = 0;
for (int i = 0; i < n; i++) {
ans = ans + a[i] - b[i];
}
return max(ans, 0LL);
}
long long solve(int nn, int kk, int *aa, int *bb)
{
n = nn;
k = kk;
a = aa;
b = bb;
calcSb();
calcPrefMats();
calcSufMats();
long long ans = getSimpleAns();
DpMatrix::mult(pref[n-1], DpVector::id, auxvec[0]);
ans = max(ans, max(auxvec[0].a, auxvec[0].b));
for (int i = 1; i < n; i++) {
DpMatrix::mult(suf[i], DpVector::id, auxvec[0]);
DpMatrix::mult(pref[i-1], auxvec[0], auxvec[1]);
ans = max(ans, max(auxvec[1].a, auxvec[1].b));
}
return ans;
}
