#include <bits/stdc++.h>
#include "homecoming.h"
// #define int long long
using namespace std;
const long long NMax = 1e6 + 100, inf = 2e9;
long long n, k, a[NMax * 3], b[NMax * 3], pref[NMax * 3];
long long f(long long i, long long x, long long y)
{
if(x == 0)
return 0;
if(y == 0)
return a[i] - (pref[i + k - 1] - pref[i - 1]);
return a[i] - b[i];
}
long long f2(long long i, long long x, long long y)
{
if(y == 0)
return 0;
if(x == 0)
return a[i] - (pref[i + k - 1] - pref[i - 1]);
return a[i] - b[i + k - 1];
}
long long solve(int N, int K, int *A, int *B)
{
long long n = N, k = K;
for(long long i = 1; i <= n; i++)
a[i] = A[i - 1];
for(long long i = 1; i <= n; i++)
{
b[i] = B[i - 1];
pref[i] = pref[i - 1] + b[i];
}
for(long long i = n + 1; i <= n * 3; i++)
{
a[i] = a[i - n];
b[i] = b[i - n];
pref[i] = pref[i - 1] + b[i];
}
// cout << f2(2, 0, 1);
// return 0;
long long suf[n + 5][2][2] = {};
for(long long i = 0; i <= n * 2; i++)
{
for(long long k = 0; k < 2; k++)
suf[i][k][0] = suf[i][k][1] = -inf;
}
suf[n][0][0] = 0;
suf[n][1][1] = f(n, 1, 0);
for(long long i = n - 1; i >= 1; i--)
{
for(long long k1 = 0; k1 < 2; k1++)
{
for(long long k2 = 0; k2 < 2; k2++)
{
for(long long z = 0; z < 2; z++)
suf[i][k1][k2] = max(suf[i][k1][k2], f(i, k1, z) + suf[i + 1][z][k2]);
}
}
}
long long pre[n * 2 + 5][2][2];
for(long long i = 0; i <= n * 2; i++)
{
for(long long k = 0; k < 2; k++)
pre[i][k][0] = pre[i][k][1] = -inf;
}
pre[n + 1][0][0] = 0;
pre[n + 1][1][1] = f2(n + 1, 0, 1);
for(long long i = n + 2; i <= n * 2; i++)
{
for(long long k1 = 0; k1 < 2; k1++)
{
for(long long k2 = 0; k2 < 2; k2++)
{
for(long long z = 0; z < 2; z++)
pre[i][k1][k2] = max(pre[i][k1][k2], f2(i, z, k2) + pre[i - 1][k1][z]);
}
}
}
long long mx = 0;
for(long long i = 1; i <= n; i++)
{
long long j = i + n - 1;
for(long long x = 0; x < 2; x++)
{
for(long long y = 0; y < 2; y++)
{
for(long long z = 0; z < 2; z++)
{
for(long long h = 0; h < 2; h++)
{
mx = max(mx, suf[i][x][y] + pre[j][z][h] + f(n, y, z));
}
}
}
}
}
return mx;
// cout << mx << '\n';
}
