#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
const long long NN = 1e6 + 10;
long long pref[NN * 3];
long long arr[NN * 3], brr[NN * 3];
long long n, k;
long long f(long long i, long long x, long long y)
{
if(x == 0)
return 0;
if(y == 0)
return (arr[i] - (pref[i + k - 1] - pref[i - 1]));
return arr[i] - brr[i];
}
long long f2(long long i, long long x, long long y)
{
if(y == 0)
return 0ll;
if(x == 0)
return arr[i] - (pref[i + k - 1] - pref[i - 1]);
return arr[i] - brr[i + k - 1];
}
long long solve(int N, int K, int *A, int *B)
{
n = N, k = K;
if(K == 1)
{
long long sum = 0;
for(long long i = 0; i < N; i++)
sum += max(0, A[i] - B[i]);
return sum;
}
for(long long i = 0; i < N * 3; i++)
{
arr[i] = A[i % N];
brr[i] = B[i % N];
}
pref[0] = brr[0];
for(long long i = 1; i < N * 3; i++)
pref[i] = pref[i - 1] + brr[i];
long long dp1[N][3][3], dp2[N][3][3];
for(long long i = 0; i < N; i++)
{
for(long long k2 = 0; k2 < 2; k2++)
dp1[i][k2][0] = dp1[i][k2][1] = dp2[i][k2][0] = dp2[i][k2][1] = -1e9;
}
dp1[N - 1][0][0] = 0;
dp1[N - 1][1][1] = f(N - 1, 1, 0);
for(long long i = N - 2; i >= 0; i--)
{
for(long long p = 0; p < 2; p++)
{
for(long long z = 0; z < 2; z++)
{
for(long long h = 0; h < 2; h++)
dp1[i][p][z] = max(dp1[i][p][z], dp1[i + 1][h][z] + f(i, p, h));
}
}
}
dp2[0][0][0] = 0;
dp2[0][1][1] = f2(N, 0, 1);
for(long long i = 1; i < N; i++)
{
for(long long p = 0; p < 2; p++)
{
for(long long z = 0; z < 2; z++)
{
for(long long h = 0; h < 2; h++)
dp2[i][p][z] = max(dp2[i][p][z], dp2[i - 1][p][h] + f2(i, h, z));
}
}
}
long long mx = 0;
for(long long i = 0; i < N; i++)
mx += (A[i] - B[i]);
for(long long i = 0; i < N; i++)
{
long long j = i - 1;
for(long long h = 0; h < 2; h++)
{
for(long long z = 0; z < 2; z++)
{
for(long long p = 0; p < 2; p++)
{
if(i == 0)
mx = max(mx, dp1[i][0][h]);
else
{
long long res = dp1[i][0][h] + dp2[j][z][p];
if(h && z && K > 1)
res = res + pref[K - 2];
mx = max(mx, res);
}
}
}
}
}
return mx;
}
