#include "homecoming.h"
#define N 2000000
#define INF 0x3f3f3f3f3f3f3f3fLL
long long max(long long a, long long b) { return a > b ? a : b; }
long long solve(int n, int k, int *aa, int *bb) {
static long long pp[N * 2];
int i;
long long p, ans, x, y;
for (i = 0, p = 0; i < n * 2; i++)
pp[i] = p += bb[i % n];
ans = 0;
x = y = 0;
for (i = 0; i < n; i++) {
long long z = max(x, y - (i == 0 ? 0 : pp[i - 1]));
ans = max(ans, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
x = max(x, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
y = max(y, z + aa[i] + (i == 0 ? 0 : pp[i - 1]));
}
x = y = -INF;
for (i = 0; i < n; i++) {
long long z = max(max(x, y - (i == 0 ? 0 : pp[i - 1])), -pp[i - 1]);
ans = max(ans, z + aa[i] - (pp[n - 1] - (i == 0 ? 0 : pp[i - 1])));
x = max(x, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
y = max(y, z + aa[i] + (i == 0 ? 0 : pp[i - 1]));
}
return ans;
}
