#include <bits/stdc++.h>
#define int __int128
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
    if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
    *pp++=ch;
}
inline void pcc(){
    fwrite(buf2,1,pp-buf2,stdout);
    pp=buf2;
}
inline int read(void){
    int w=1;
    register int x(0);register char c(getchar());
    while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w*x;
}
void write(int x){
    static int sta[20];
    int top=0;
    do{
        sta[top++]=x%10,x/=10;
    }while(x);
    while(top) pc(sta[--top]+48);
}
void we(int x){
    write(x);
    pc('\n');
}
int T,N,M,K,C,a[1000009],rr[1000009],ff[1000009],su[1000009];
int dp[1000009],laz[30000009],ls[30000009],rs[30000009],kk,rt;
inline int fx(int x) {
    return (x%K)*(K-C);
}
#define md ((l+r)>>1)
int nw() {
    ++kk;
    laz[kk]=ls[kk]=rs[kk]=0;
    return kk;
}
void up(int& n,int l,int r,int L,int R,int v) {
    if(r<L||R<l) return;
    if(!n) {
        n=nw();
    }
    if(L<=l&&r<=R) {
        laz[n]=v;
        return;
    }
    if(laz[n]) {
        if(!ls[n]) ls[n]=nw();
        if(!rs[n]) rs[n]=nw();
        laz[ls[n]]=laz[n];
        laz[rs[n]]=laz[n];
        laz[n]=0;
    }
    up(ls[n],l,md,L,R,v);
    up(rs[n],md+1,r,L,R,v);
}
int qr(int n,int l,int r,int p) {
    if(laz[n]) return laz[n];
    if(p<=md) return qr(ls[n],l,md,p);
    return qr(rs[n],md+1,r,p);
}
signed main(void) {
    T=read();
    int inf=1;
    for(int i=1;i<=36;i++) inf*=10;
    while(T--) {
        N=read();M=read();K=read();C=read();
        int ans=0;
        for(int i=1;i<=N;i++) {
            a[i]=read();
            ans+=a[i];
            su[i]=a[i]+su[i-1];
            ff[i]=su[i]-su[std::max(i-M+1,(__int128)0)];
        }
        if(C==1) {
            int p=1;
            while(1) {
                while(p<=N&&(a[p]==0)) p++;
                if(p>N) break;
                ans-=(a[p]/K)*(K-C);
                a[p]%=K;
                while(p<=N&&(a[p]==0)) p++;
                if(p>N) break;
                int su=0;
                for(int i=p;i<p+M&&i<=N;i++) {
                    su+=a[i];
                }
                int le=K;
                for(int i=p;i<p+M&&i<=N;i++) {
                    int tq=std::min(a[i],le);
                    le-=tq;a[i]-=tq;
                }
                ans-=(K-le)-C;
            }
            printf("%lld\n",(long long)(ans));            
            continue;
        }
        rt=0;kk=0;
        up(rt,0,K-1,0,K-1,N);
        for(int i=N;i>=1;i--) {
            int ww=su[i]%K;
            if(ww>ff[i]) {
                if(ww<=K-2) up(rt,0,K-1,ww+1,K-1,i);
                up(rt,0,K-1,0,ww-ff[i]-1,i);
            } else if(ff[i]<=K-2) up(rt,0,K-1,ww+1,ww-ff[i]-1+K,i);
            rr[i]=qr(rt,0,K-1,su[i-1]%K);
        }
        dp[N+1]=0;
        for(int i=N;i>=1;i--) {
            dp[i]=inf;
            int ss=su[rr[i]]-su[i-1];
            ss%=K;
            dp[i]=std::min(dp[i],dp[rr[i]+1]+C*(K-ss));
            for(int j=rr[i];j>=i&&dp[i]>dp[j+1];j--) {
                dp[i]=std::min(dp[i],dp[j+1]+(su[j]-su[i-1])%K*(K-C));
            }
        }
        printf("%lld\n",(long long)((dp[1]+ans*C)/K));
    }
}