// Bogdan Ciobanu
// O(N)
#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct Flow {
int64 from, to, limit;
Flow() = default;
Flow(int64 from_, int64 to_, int64 limit_)
: from(from_), to(to_), limit(limit_) {}
};
int64 solve(int n, int k, int* a_, int* b_) {
vector<int64> a(n), b(n);
for (int i = 0; i < n; ++i) {
a[i] = a_[i];
b[i] = b_[i];
}
int64 result = accumulate(a.begin(), a.end(), 0LL);
deque<Flow> flows;
int64 start_layer = 0, end_layer = accumulate(b.begin(), b.begin() + k, 0LL);
int64 pushed_front = 0, cycle_layer = 0;
function<int64(int64)> PushBack = [&](int64 mx) -> int64 {
int64 from = start_layer;
if (not flows.empty() and from <= flows.back().to) {
from = flows.back().to + 1;
}
if (mx > end_layer - from) {
mx = end_layer - from;
}
if (mx <= 0) {
return 0;
}
flows.emplace_back(from, from + mx - 1, end_layer);
return mx;
};
function<int64(int64)> PushFront = [&](int64 mx) -> int64 {
if (mx == 0) return 0;
int64 r = pushed_front + mx - 1;
int64 mn_move = 1LL << 62, sum_used = 0;
while (not flows.empty() and flows.front().from <= r) {
int64 dif = min(r - flows.front().from + 1,
flows.front().limit - flows.front().to - 1);
mx -= r - flows.front().from + 1 - dif;
r = flows.front().to + dif;
mn_move = min(mn_move, flows.front().limit - r - 1);
sum_used += flows.front().to - flows.front().from + 1;
flows.pop_front();
}
if (sum_used != 0) {
flows.emplace_front(pushed_front + mx,
pushed_front + mx + sum_used - 1,
pushed_front + mx + sum_used + mn_move);
}
return mx;
};
for (int i = 0; i < n; ++i) {
int64 pushed = PushBack(a[i]);
a[i] -= pushed;
result -= pushed;
if (i + k > n) {
cycle_layer += b[(i + k - 1) % n];
pushed_front += PushFront(min(a[i], cycle_layer - pushed_front));
}
start_layer += b[i];
if (i + k < n) {
end_layer += b[i + k];
}
}
result -= pushed_front;
return result;
}
