#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
long long solve(int n, int k, int l, const vector<int>& L, const vector<int>& R, const vector<long long>& prefL, const vector<long long>& prefR, int mid){
if(mid > (int)L.size() + (int)R.size()){
return 1e18;
}
long long ans = 1e18;
for(int j = max(0, mid - (int)L.size()); j <= min(mid, (int)R.size()); j++){
long long thing = (mid + (k - 1))/k;
thing *= l;
int i = (int)L.size() + j - mid;
long long thing2 = (i == 0 ? 0 : prefL[i - 1]) + (j == (int)R.size() ? 0 : prefR[j]);
ans = min(ans, thing + thing2);
}
return ans;
}
long long delivery(int n, int k, int l, int p[]){
vector<int> L;
vector<int> R;
for(int i = 0; i < n; i++){
if(p[i] <= l/2){
L.push_back(p[i]);
}
else{
R.push_back(p[i]);
}
}
vector<long long> prefL((int)L.size());
for(int i = 0; i < min((int)L.size(), k); i++){
prefL[i] = 2 * L[i];
}
for(int i = k; i < (int)L.size(); i++){
prefL[i] = prefL[i - k] + 2 * L[i];
}
vector<long long> prefR((int)R.size());
for(int i = (int)R.size() - 1; i >= max(0, (int)R.size() - k); i--){
prefR[i] = 2 * (l - R[i]);
}
for(int i = (int)R.size() - k - 1; i >= 0; i--){
prefR[i] = prefR[i + k] + 2 * (l - R[i]);
}
// long long res = 1e18;
// for(int i = 0; i <= (long long)L.size() + (long long)R.size(); i++){
// if(i % k == 0){
// res = min(res, solve(n, k, l, L, R, prefL, prefR, i));
// // cout << solve(n, k, l, L, R, prefL, prefR, i) << " ";
// }
// }
// // cout << "\n";
int low = 0;
int high = ((int)L.size() + (int)R.size())/k;
long long res = 1e18;
while(low <= high){
int mid = (low + high)/2;
res = min(res, solve(n, k, l, L, R, prefL, prefR, mid * k));
if(solve(n, k, l, L, R, prefL, prefR, mid * k) > solve(n, k, l, L, R, prefL, prefR, mid * k + k)){
low = mid + 1;
}
else{
high = mid - 1;
}
}
return res;
}
// int main(){
// int n, k, l;
// cin >> n >> k >> l;
// int p[n];
// for(int i = 0; i < n; i++){
// cin >> p[i];
// }
// cout << delivery(n, k, l, p) << "\n";
// }
