#include <bits/stdc++.h>
// #include <windows.h>
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
using namespace std;
//#pragma GCC optimize(3)
#define DB double
#define LL long long
#define ULL unsigned long long
#define in128 __int128
#define cint const int
#define cLL const LL
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)
#define For_(z,e1,e2) for(int z=(e1);z<(e2);z++)
#define Rof_(z,e1,e2) for(int z=(e2);z>(e1);z--)
#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define inpr(e1,e2) scanf("%d%d",&e1,&e2)
#define in3(e1,e2,e3) scanf("%d%d%d",&e1,&e2,&e3)
#define outint(e) printf("%d\n",e)
#define outint_(e) printf("%d%c",e," \n"[i==n])
#define outint2_(e,e1,e2) printf("%d%c",e," \n"[(e1)==(e2)])
#define outll(e) printf("%lld\n",e)
#define outll_(e) printf("%lld%c",e," \n"[i==n])
#define outll2_(e,e1,e2) printf("%lld%c",e," \n"[(e1)==(e2)])
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define ll(e) (1ll*(e))
#define pb push_back
#define ft first
#define sc second
#define pii pair<int,int> 
#define pli pair<long long,int> 
#define vct vector 
#define clean(e) while(!e.empty()) e.pop()
#define all(ev) ev.begin(),ev.end()
#define sz(ev) ((int)ev.size())
#define debug(x) printf("%s=%d\n",#x,x)
#define x0 __xx00__
#define y0 __yy00__
#define y1 __yy11__
#define ffo fflush(stdout)
cLL mod=998244353ll,G=404ll;
// cLL mod=1000000007ll;
// cLL mod[2]={1686688681ll,1666888681ll},base[2]={166686661ll,188868881ll};
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; } template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type up_div(Type w1,Type w2) { return (w1/w2+(w1%w2?1:0)); }
template <typename Type> Type gcd(Type X_,Type Y_) { Type R_=X_%Y_; while(R_) { X_=Y_; Y_=R_; R_=X_%Y_; } return Y_; } template <typename Type> Type lcm(Type X_,Type Y_) { return (X_/gcd(X_,Y_)*Y_); }
template <typename Type> Type md(Type w1,const Type w2=mod) { w1%=w2; if(w1<0) w1+=w2; return w1; } template <typename Type> Type md_(Type w1,const Type w2=mod) { w1%=w2; if(w1<=0) w1+=w2; return w1; }
void ex_gcd(LL &X_,LL &Y_,LL A_,LL B_) { if(!B_) { X_=1ll; Y_=0ll; return ; } ex_gcd(Y_,X_,B_,A_%B_); X_=md(X_,B_); Y_=(1ll-X_*A_)/B_; } LL inv(LL A_,LL B_=mod) { LL X_=0ll,Y_=0ll; ex_gcd(X_,Y_,A_,B_); return X_; }
template <typename Type> void add(Type &w1,const Type w2,const Type M_=mod) { w1=md(w1+w2,M_); } void mul(LL &w1,cLL w2,cLL M_=mod) { w1=md(w1*md(w2,M_),M_); } template <typename Type> Type pw(Type X_,Type Y_,Type M_=mod) { Type S_=1; while(Y_) { if(Y_&1) mul(S_,X_,M_); Y_>>=1; mul(X_,X_,M_); } return S_; }
template <typename Type> Type bk(vector <Type> &V_) { auto T_=V_.back(); V_.pop_back(); return T_; } template <typename Type> Type tp(stack <Type> &V_) { auto T_=V_.top(); V_.pop(); return T_; } template <typename Type> Type frt(queue <Type> &V_) { auto T_=V_.front(); V_.pop(); return T_; }
template <typename Type> Type bg(set <Type> &V_) { auto T_=*V_.begin(); V_.erase(V_.begin()); return T_; } template <typename Type> Type bk(set <Type> &V_) { auto T_=*prev(V_.end()); V_.erase(*prev(V_.end())); return T_; }
mt19937 gen(time(NULL)); int rd() { return abs((int)gen()); }
int rnd(int l,int r) { return rd()%(r-l+1)+l; }

void main_init()
{

}
cint N=4.01e5;
int n,n2,m;
LL d;
cLL inf=1e18;
LL a[N],s[N];
LL sum(int l,int r)
{
    return (s[r]-s[l-1]);
}
LL calc(int l,int r)
{
    return (sum(l+r+1>>1,r)-sum(l,l+r>>1));
}
pli dp[N],dp2[N];
int pre[N],pre2[N];
pli check(int L,int R,LL w)
{
    deque <array<int,2>> q;
    q.push_back({L-1,L});
    auto fun=[&](int j,int i)
    {
        return (pli){dp[j].ft+calc(j+1,i)+w,dp[j].sc+1};
    };
    dp[L-1]={0ll,0},pre[L-1]=L-1;
    For(i,L,R)
    {
        // printf("%d->%d\n",i,q.front()[0]);
        dp[i]=fun(q.front()[0],i);
        pre[i]=q.front()[0];
        if(sz(q)>1&&q[1][1]==i+1||i==R) q.pop_front();
        else q[0][1]++;
        int lst=R+1;
        while(!q.empty()&&fun(i,q.back()[1])<fun(q.back()[0],q.back()[1]))
            lst=q.back()[1],q.pop_back();
        if(!q.empty())
        {
            int l=q.back()[1],r=lst,mid;
            while(l+1<r)
            {
                mid=l+r>>1;
                (fun(i,mid)<fun(q.back()[0],mid)?r:l)=mid;
            }
            lst=r;
        }
        if(lst<=R) q.push_back({i,lst});
    }
    // For(i,1,n) printf("%lld,%d\n",dp[i].ft,dp[i].sc);
    // puts("");
    return dp[R];
}
pli check2(int L,int R,LL w)
{
    deque <array<int,2>> q;
    q.push_back({L-1,L});
    auto fun=[&](int j,int i)
    {
        return (pli){dp2[j].ft+calc(j+1,i)+w,dp2[j].sc-1};
    };
    dp2[L-1]={0ll,0},pre2[L-1]=L-1;
    For(i,L,R)
    {
        // printf("%d->%d\n",i,q.front()[0]);
        dp2[i]=fun(q.front()[0],i);
        pre2[i]=q.front()[0];
        if(sz(q)>1&&q[1][1]==i+1||i==R) q.pop_front();
        else q[0][1]++;
        int lst=R+1;
        while(!q.empty()&&fun(i,q.back()[1])<fun(q.back()[0],q.back()[1]))
            lst=q.back()[1],q.pop_back();
        if(!q.empty())
        {
            int l=q.back()[1],r=lst,mid;
            while(l+1<r)
            {
                mid=l+r>>1;
                (fun(i,mid)<fun(q.back()[0],mid)?r:l)=mid;
            }
            lst=r;
        }
        if(lst<=R) q.push_back({i,lst});
    }
    // For(i,1,n) printf("%lld,%d\n",dp2[i].ft,dp2[i].sc);
    // puts("");
    return dp2[R];
}
void wqs(int stt)
{
    LL l=-1ll,r=inf,mid;
    while(l+1ll<r)
        (check(stt,stt+n-1,mid=l+r>>1).sc<=m?r:l)=mid;
    check(stt,stt+n-1,r); check2(stt,stt+n-1,r);
    // printf("dp\n");
    // For(i,1,n) printf("%lld,%d\n",dp[i].ft,dp[i].sc);
    // printf("dp2\n");
    For(i,1,n) dp2[i].sc=-dp2[i].sc;
    // For(i,1,n) printf("%lld,%d\n",dp2[i].ft,dp2[i].sc);
    for(int lst=n,i=n-1,j=m-1;i>=0;i--)
    {
        if(!j)
        {
            pre[i]=0;
            break;
        }
        if(dp[i].sc<=j&&j<=dp2[i].sc&&dp[i].ft+calc(i+1,lst)+r==dp[lst].ft)
        {
            // printf("%d->%d\n",lst,i);
            pre[lst]=i,lst=i,j--;
        }
    }
    // printf("[%d,%d]:%d\n",dp[n].sc,dp2[n].sc,m);
}
int pst[N];
vct <pli> trans(int l1,int r1,int l2,int r2,vct <pli> &f1)
{
    // printf("trans: [%d,%d]->[%d,%d]\n",l1,r1,l2,r2);
    vct <pli> f2(r2-l2+1);
    auto fun=[&](int j,int i)->LL
    {
        return f1[j-l1].ft+calc(j+1,i);
    };
    auto solve=[&](int l,int r,int L,int R,auto &self)
    {
        ret(L>R);
        // printf("[%d,%d],[%d,%d]\n",l,r,L,R);
        int M=L+R>>1;
        int m=l; LL mn=inf;
        For(i,l,min(r,M-1))
        {
            LL w=fun(i,M);
            if(w<mn) mn=w,m=i;
        }
        f2[M-l2]={mn,m};
        self(l,m,L,M-1,self);
        self(m,r,M+1,R,self);
    };
    solve(l1,r1,l2,r2,solve);
    // printf("stop\n");
    return f2;
}
LL ans;
vct <int> solu;
void solve(vct <array<int,2>> v)
{
    auto [l,r]=v[0]; ret(l>r);
    // printf("solve [%d,%d]\n",l,r); ffo;
    int mid=l+r>>1;
    vct <pli> stt(r-l+1,(pli){inf,0});
    stt[mid-l]={0ll,0};
    vct <vct<pli>> gt; gt.pb(stt);
    For(i,1,m)
        gt.pb(trans(v[i-1][0],v[i-1][1],v[i][0],v[i][1],gt.back()));
    vct <array<int,2>> v1,v2;
    for(int i=m,t=mid+n;i>=0;(i?(t=gt[i][t-v[i][0]].sc):0),i--)
    {
        // printf("i=%d,t=%d\n",i,t);
        v1.pb({v[i][0],t});
        v2.pb({t,v[i][1]});
    }
    reverse(all(v1)); reverse(all(v2));
    if(gt[m][mid-l].ft<ans)
    {
        ans=gt[m][mid-l].ft;
        solu.clear();
        for(int i=m,t=mid+n;i>=0;(i?(t=gt[i][t-v[i][0]].sc):0),i--)
            solu.pb(t);
    }
    v1[0][1]--,v1[m][1]--;
    v2[0][0]++,v2[m][0]++;
    solve(v1),solve(v2);
}
LL a_[N];
void main_solve()
{
    inpr(n,m); inll(d);
    For(i,1,n) inll(a[i]);
    For(i,1,n) a_[i]=a[i];
    sort(a+1,a+n+1);
    For(i,1,n) a[i+n]=a[i]+d;
    For(i,1,n) s[i]=s[i-1]+a[i];
    wqs(1);
    pst[m]=n; Rof(i,1,m-1) pst[i]=pre[pst[i+1]];
    int mn=n+1,gt=0;
    For(i,1,m) if(pst[i]-pst[i-1]<mn)
    {
        mn=pst[i]-pst[i-1];
        gt=i;
    }
    int stt=pst[gt-1]+1;
    For(i,1,n) a[i+n]=a[i]+d;
    For(i,stt,stt+n-1) a[i-stt+1]=a[i];
    For(i,1,n) a[i+n]=a[i]+d;
    n2=n<<1;
    For(i,1,n2) s[i]=s[i-1]+a[i];
    vct <int> h;
    For(i,gt,m) h.pb(pst[i]-pst[i-1]);
    For_(i,1,gt) h.pb(pst[i]-pst[i-1]);
    For(i,1,m) pst[i]=pst[i-1]+h[i-1];
    vct <array<int,2>> v;
    For(i,1,m) v.pb({pst[i-1],pst[i]});
    v.pb({v[0][0]+n,v[0][1]+n});
    ans=inf;
    // For(i,1,n2) outll2_(a[i],i,n2);
    // for(auto [l,r]:v) printf("> [%d,%d]\n",l,r);
    solve(v);
    // printf("???\n"); return ;
    outll(ans);
    // return ;
    // solu.pop_back();
    reverse(all(solu));
    vct <LL> Solu;
    For(i,1,m)
        Solu.pb(md(a[solu[i-1]+solu[i]+1>>1],d));
    sort(all(Solu));
    For_(i,0,m) outll2_(Solu[i],i,m-1);
    // LL ck=0ll;
    // auto dis=[&](LL w1,LL w2)->LL
    // {
    //     LL t=llabs(w1-w2);
    //     return min(t,d-t);
    // };
    // For(i,1,n)
    // {
    //     LL mn=inf;
    //     for(auto w:Solu)
    //         get_min(mn,dis(a_[i],w));
    //     ck+=mn;
    // }
    // outll(ck);
    // if(ck!=ans)
    // {
    //     printf("Boom\n");
    //     ffo;
    // }
}
int main()
{
    // ios::sync_with_stdio(0); cin.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // srand(time(NULL));
    main_init();
    // int _; inint(_); For(__,1,_) // T>1 ?
        // printf("\n------------\n\n"),
        main_solve();
    // cerr<<clock()<<'\n';
    return 0;
}
/*

*/