#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<ll> forwardDistances, backwardDistances;
vector<ll> memoForward, memoBackward;
ll computeForwardTime(ll idx, ll stepSize) {
if (idx < 0) return 0;
if (memoForward[idx] != -1) return memoForward[idx];
return memoForward[idx] = 2LL * forwardDistances[idx] + computeForwardTime(idx - stepSize, stepSize);
}
ll computeBackwardTime(ll idx, ll stepSize) {
if (idx < 0) return 0;
if (memoBackward[idx] != -1) return memoBackward[idx];
return memoBackward[idx] = 2LL * backwardDistances[idx] + computeBackwardTime(idx - stepSize, stepSize);
}
ll delivery(int numCheckpoints, int stepSize, int trackLength, int* checkpoints) {
forwardDistances.clear();
backwardDistances.clear();
for (int i = 0; i < numCheckpoints; i++) {
ll pos = checkpoints[i];
if (pos == 0 || pos == trackLength) continue;
if (2 * pos > trackLength)
backwardDistances.push_back(trackLength - pos);
else
forwardDistances.push_back(pos);
}
sort(forwardDistances.begin(), forwardDistances.end());
sort(backwardDistances.begin(), backwardDistances.end());
memoForward.assign(forwardDistances.size(), -1);
memoBackward.assign(backwardDistances.size(), -1);
ll fCount = forwardDistances.size();
ll bCount = backwardDistances.size();
ll result = computeForwardTime(fCount - 1, stepSize) + computeBackwardTime(bCount - 1, stepSize);
for (ll i = 0; i <= stepSize; ++i) {
ll skipF = fCount - 1 - i;
ll skipB = bCount - 1 - (stepSize - i);
ll timeF = computeForwardTime(skipF, stepSize);
ll timeB = computeBackwardTime(skipB, stepSize);
result = min(result, timeF + timeB + trackLength);
}
return result;
}
