#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
const ll INF = 1e18;
using mat = array<array<ll, 2>, 2>;
mat mul(mat a, mat b) {
mat c = {-INF, -INF, -INF, -INF};
forn(i, 2) forn(k, 2) forn(j, 2) {
c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
}
return c;
}
ll solve(int N, int K, int *A, int *B) {
vi a(N), b(N);
forn(i, N) a[i] = A[i], b[i] = B[i];
ll ret = accumulate(all(a), 0LL) - accumulate(all(b), 0LL);
vll pref(3 * N + 10);
forn(i, 3 * N + 9) pref[i + 1] = pref[i] + b[i % N];
int s = 1;
while (s < 2 * N) s *= 2;
vector<mat> st(2 * s, {0, -INF, -INF, 0});
forn(i, 2 * N) {
st[i + s] = {0, -pref[i + K] + pref[i] + a[i % N], 0, -b[(i + K - 1) % N] + a[i % N]};
}
dforsn(i, 1, s) st[i] = mul(st[2 * i], st[2 * i + 1]);
forn(start, N) {
mat leftRet = {0, -INF, -INF, 0};
mat rightRet = {0, -INF, -INF, 0};
for (int l = start + s, r = start + N + s; l < r; l /= 2, r /= 2) {
if (l & 1) leftRet = mul(leftRet, st[l++]);
if (r & 1) rightRet = mul(st[--r], rightRet);
}
mat curr = mul(leftRet, rightRet);
ret = max({ret, curr[0][0], curr[0][1]});
}
return ret;
}
/*int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int a[] = {40, 80, 100};
int b[] = {140, 0, 20};
cout << solve(3, 2, a, b) << "\n";
return 0;
}*/
