#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[1010][1010][2], dp2[15][15][15][2];
vector<int> a;
int N, K, L;
ll solve(int l, int r, int side) {
if(l == r - 1) {
if(!side) return min(a[l], L - a[l]);
else return min(a[r], L - a[r]);
}
ll &ret = dp[l][r][side];
if(ret != -1) return ret;
if(side == 0) {
ret = solve(l + 1, r, 0) + a[l + 1] - a[l];
ret = min(ret, solve(l, r - 1, 1) + a[l] + L - a[r - 1]);
} else {
ret = solve(l, r - 1, 1) + a[r] - a[r - 1];
ret = min(ret, solve(l + 1, r, 0) + a[l + 1] + L - a[r]);
}
return ret;
}
ll solve2(int l, int r, int rem, int side) {
if(l == r - 1) {
if(!side) return min(a[l], L - a[l]);
else return min(a[r], L - a[r]);
}
ll &ret = dp2[l][r][rem][side];
if(ret != -1) return ret;
if(!side) {
if(rem) {
ret = solve2(l + 1, r, rem - 1, 0) + a[l + 1] - a[l];
ret = min(ret, solve2(l, r - 1, K - 1, 1) + a[l] + L - a[r - 1]);
} else {
ret = solve2(l + 1, r, K - 1, 0) + a[l + 1];
ret = min(ret, solve2(l, r - 1, K - 1, 1) + L - a[r - 1]);
ret += a[l];
}
} else {
if(rem) {
ret = solve2(l, r - 1, rem - 1, 1) + a[r] - a[r - 1];
ret = min(ret, solve2(l + 1, r, K - 1, 0) + a[l + 1] + L - a[r]);
} else {
ret = solve2(l, r - 1, K - 1, 1) + L - a[r - 1];
ret = min(ret, solve2(l + 1, r, K - 1, 0) + a[l + 1]);
ret += L - a[r];
}
}
return ret;
}
ll delivery(int n, int k, int l, int p[]) {
N = n, K = k, L = l;
if(K == 1 || N == 1) {
ll tot = 0;
for(int i = 0; i < N; i++)
tot += 2 * min(p[i], L - p[i]);
return tot;
}
if(N == K) {
memset(dp, -1, sizeof dp);
a.push_back(0);
for(int i = 0; i < N; i++)
a.push_back(p[i]);
a.push_back(L);
return solve(0, N + 1, 0);
}
if(N <= 15) {
memset(dp2, -1, sizeof dp2);
a.push_back(0);
for(int i = 0; i < N; i++)
a.push_back(p[i]);
a.push_back(L);
return solve2(0, N + 1, K, 0);
}
}
