#include "homecoming.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
int K, *A, *B;
long long *sB, x[2000009], y[2000009];
long long getSB (int i, int j)
{
if (i > j) return 0;
if (i == 0) return sB[j];
return sB[j] - sB[i - 1];
}
long long solve (int N, int kk, int *aa, int *bb)
{
A = new int[2 * N], B = new int[2 * N];
sB = new long long[2 * N], K = kk;
for (int i=0; i<N; i++)
A[i] = A[N + i] = aa[i], B[i] = B[N + i] = bb[i];
sB[0] = B[0];
for (int i=1; i<2 * N; i++)
sB[i] = sB[i - 1] + B[i];
long long ans = 0;
for (int i=0; i<N; i++)
ans += A[i] - B[i];
ans = max (ans, 0LL);
if (N == K)
return ans;
x[0] = -INF, y[0] = 0;
for (int i=1; i<N; i++)
{
x[i] = max (x[i - 1] + A[i] - B[i + K - 1], y[i - 1] + A[i] - getSB (i, i + K - 1));
y[i] = max (x[i - 1], y[i - 1]);
}
ans = max (ans, max (x[N - 1], y[N - 1]));
x[0] = A[0] - getSB (0, K - 1);
y[0] = -INF;
for (int i=1; i<N; i++)
{
long long c0 = (i + K - 1 >= N ? 0 : B[i + K - 1]);
int l = i, r = min (i + K - 1, N - 1);
long long c1 = getSB (l, r);
x[i] = max (x[i - 1] + A[i] - c0, y[i - 1] + A[i] - c1);
y[i] = max (x[i - 1], y[i - 1]);
}
ans = max (ans, max (x[N - 1], y[N - 1]));
return ans;
}
