#include "boxes.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
vector <ll> val_cw, val_ccw, cf_cw, cf_ccw;
vector <pair<ll, ll>> op_cw, op_ccw, cw, ccw;;
ll s_cw, s_ccw, add, shift_cw, shift_ccw, n_cw, n_ccw, n, k;
ll ans_cw, ans_ccw, ans, add_cw, add_ccw, l;
void process_cw(ll x, bool flag) {
if (s_cw == 0) {
op_cw.clear();
return;
}
if (flag) {
ll i = n_cw - 1; op_cw.clear();
op_cw.pb({1, ans_cw});
op_cw.pb({2, s_cw});
while (x > 0 && i >= 0) {
while (x > 0 && cw[i].se > 0) {
cw[i].se--; x--; op_cw.pb({3, i});
}
i--;
}
ans_cw = 0; s_cw = 0;
for (ll i = n_cw - 1; i >= 0; i--) {
s_cw += cw[i].se;
// val_cw[s_cw % k] += cf_cw[i];
ans_cw += (ll)((s_cw + k - 1) / k) * (ll)cf_cw[i];
}
} else {
ll i = n_cw - 1;
while (cw[i].se == 0)
i--;
add_cw += (ll)cw[i].fi;
while (x > 0 && i >= 0) {
while (x > 0 && cw[i].se > 0) {
cw[i].se--; x--;
}
i--;
}
ans_cw = 0; s_cw = 0;
for (ll i = n_cw - 1; i >= 0; i--) {
s_cw += cw[i].se;
// val_cw[s_cw % k] += cf_cw[i];
ans_cw += (ll)((s_cw + k - 1) / k) * (ll)cf_cw[i];
}
}
}
void roll_back_cw() {
while (op_cw.size() != 0) {
ll type = op_cw[op_cw.size() - 1].fi, x = op_cw[op_cw.size() - 1].se;
op_cw.pop_back();
if (type == 1) {
ans_cw = x;
} else if (type == 2) {
s_cw = x;
} else if (type == 3) {
cw[x].se++;
}
}
}
void process_ccw(ll x, bool flag) {
if (s_ccw == 0) {
op_ccw.clear();
return;
}
// cout << "Fds " << endl;
// cout << x << " " << flag << endl;
if (flag) {
ll i = n_ccw - 1; op_ccw.clear();
op_ccw.pb({1, ans_ccw});
op_ccw.pb({2, s_ccw});
while (x > 0 && i >= 0) {
while (x > 0 && ccw[i].se > 0) {
ccw[i].se--; x--; op_ccw.pb({3, i});
}
// cout << x << " " << i << endl;
i--;
}
// cout << x << " " << i << endl;
ans_ccw = 0; s_ccw = 0;
for (ll i = n_ccw - 1; i >= 0; i--) {
s_ccw += ccw[i].se;
val_ccw[s_ccw % k] += cf_ccw[i];
ans_ccw += (ll)((s_ccw + k - 1) / k) * (ll)cf_ccw[i];
}
} else {
ll i = n_ccw - 1;
while (ccw[i].se == 0)
i--;
add_ccw += (ll)l - (ll)ccw[i].fi;
while (x > 0 && i >= 0) {
while (x > 0 && ccw[i].se > 0) {
ccw[i].se--; x--;
}
i--;
}
ans_ccw = 0; s_ccw = 0;
for (ll i = n_ccw - 1; i >= 0; i--) {
s_ccw += ccw[i].se;
// val_ccw[s_ccw % k] += cf_ccw[i];
ans_ccw += (ll)((s_ccw + k - 1) / k) * (ll)cf_ccw[i];
}
}
}
void roll_back_ccw() {
while (op_ccw.size() != 0) {
ll type = op_ccw[op_ccw.size() - 1].fi, x = op_ccw[op_ccw.size() - 1].se;
op_ccw.pop_back();
if (type == 1) {
ans_ccw = x;
} else if (type == 2) {
s_ccw = x;
} else if (type == 3) {
ccw[x].se++;
}
}
}
// ll delivery(int n1, int k1, int l1, vector <ll> p) {
ll delivery(int n1, int k1, int l1, int p1[]) {
vector <ll> p = {};
for (ll i = 0; i < n1; i++)
p.pb(p1[i]);
n = n1; k = k1; l = l1;
if (n > 3010 || k > 3010)
return 0;
sort(p.begin(), p.end());
add = 0;
cw.clear(); ccw.clear(); ll cnt0 = 0;
for (ll i = 0; i < p.size(); i++) {
if (p[i] == 0)
cnt0++;
if (l % 2 == 0 && p[i] == l / 2) {
add++;
} else if (p[i] <= l / 2 && p[i] != 0) {
if (cw.size() == 0 || cw[cw.size() - 1].fi != p[i])
cw.pb({p[i], 0});
cw[cw.size() - 1].se++;
} else if (p[i] != 0) {
if (ccw.size() == 0 || ccw[ccw.size() - 1].fi != p[i])
ccw.pb({p[i], 0});
ccw[ccw.size() - 1].se++;
}
}
n -= cnt0;
// for (pair<ll, ll> to : cw)
// cout << to.fi << " " << to.se << endl;
// cout << endl;
// for (pair<ll, ll> to : ccw)
// cout << to.fi << " " << to.se << endl;
reverse(ccw.begin(), ccw.end());
val_cw.assign(k, 0);
val_ccw.assign(k, 0);
n_cw = cw.size();
n_ccw = ccw.size();
cf_cw.assign(n_cw, 0);
for (ll i = 0; i < n_cw; i++) {
if (i == 0)
cf_cw[i] = cw[i].fi;
else
cf_cw[i] = cw[i].fi - cw[i - 1].fi;
}
cf_ccw.assign(n_ccw, 0);
for (ll i = 0; i < n_ccw; i++) {
if (i == 0)
cf_ccw[i] = l - ccw[i].fi;
else
cf_ccw[i] = ccw[i - 1].fi - ccw[i].fi;
}
// cout << "ok" << endl;
// return 0;
ans_cw = ans_ccw = s_cw = s_ccw = shift_cw = shift_ccw = add_cw = add_ccw = 0;
for (ll i = n_cw - 1; i >= 0; i--) {
s_cw += cw[i].se;
// val_cw[s_cw % k] += cf_cw[i];
ans_cw += (ll)((s_cw + k - 1) / k) * (ll)cf_cw[i];
}
for (ll i = n_ccw - 1; i >= 0; i--) {
s_ccw += ccw[i].se;
// val_ccw[s_ccw % k] += cf_ccw[i];
ans_ccw += (ll)((s_ccw + k - 1) / k) * (ll)cf_ccw[i];
}
// cout << ans_cw << " " << ans_ccw << endl;
// return 0;
ans = (ll)((n + k - 1) / k) * (ll)l;
// cout << ans << endl; ll cur = 0;
while (true) {
// cur++;
ll cnt, mod; ll tmp;
cnt = (s_ccw + add + k - 1) / k; mod = k * cnt - (s_ccw + add);
tmp = (ll)cnt * (ll)l;
// cout << cur << " " << cnt << " " << tmp << " " << mod << endl;
process_cw(mod, true);
// if (ans_cw < 0 || add_cw < 0 || ans_ccw < 0 || add_ccw < 0)
// return -1;
// cout << cur << " " << ans_cw << " " << add_cw << " " << tmp + 2ll * (ans_cw + add_cw) << endl;
ans = min(ans, tmp + 2ll * (ans_cw + add_cw + add_ccw));
roll_back_cw();
// cout << cur << " " << ans_cw << " " << s_cw << endl;
cnt = (s_cw + add + k - 1) / k; mod = k * cnt - (s_cw + add);
tmp = (ll)cnt * (ll)l;
// cout << cur << " " << cnt << " " << tmp << " " << mod << endl;
process_ccw(mod, true);
// cout << cur << " " << ans_ccw << " " << add_ccw << " " << tmp + 2ll * (ans_ccw + add_ccw) << endl;
ans = min(ans, tmp + 2ll * (ans_ccw + add_ccw + add_cw));
roll_back_ccw();
// cout << cur << " " << ans_ccw << endl;
process_cw(k, false);
process_ccw(k, false);
cnt = (s_cw + s_ccw + add + k - 1) / k;
tmp = (ll)cnt * (ll)l;
// cout << "Dfsdf " << tmp << " " << add_cw << " " << add_ccw << " " << s_cw << " " << s_ccw << endl;
ans = min(ans, tmp + 2ll * (add_cw + add_ccw));
if (s_cw == 0 && s_ccw == 0)
break;
}
return ans;
}
