#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e7 + 10;
ll ps[MAXN], ss[MAXN], rem[MAXN], dp2[MAXN], n, k, l, f[MAXN];
// TODO: reset rem and dp2
inline void solve(ll* dp1) {
dp1[0] = 0;
dp2[0] = 0;
rem[0] = k;
for (int i = 1; i <= n; i++) {
dp1[i] = dp1[i - 1] + min(f[i], l - f[i]) + min(f[i], l - f[i]);
dp2[i] = dp1[i - 1] + min(f[i], l - f[i]);
rem[i] = k - 1;
if (rem[i - 1]) {
ll tdp = dp2[i - 1] + f[i] - f[i - 1];
ll trem = rem[i - 1] - 1;
if (pll(tdp, trem) <= pll(dp2[i], rem[i]))
dp2[i] = tdp, rem[i] = trem;
}
dp1[i] = min(dp1[i], dp2[i] + min(f[i], l - f[i]));
}
}
ll delivery(int N, int K, int L, int p[]) {
n = N, k = K, l = L;
for (int i = 0; i < n; i++)
f[i] = p[i];
f[n] = 0;
sort(f, f + n + 1);
solve(ps);
for (int i = 0; i <= n; i++)
f[i] = (l - p[i]);
f[n] = 0;
sort(f, f + n + 1);
solve(ss);
ll ans = min(ps[n], ss[n]);
for (int i = 1; i < n; i++)
ans = min(ans, ps[i] + ss[n - i]);
return ans;
}
