#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];
int dp[1000009];
inline int fx(int x) {
    return (x%K)*(K-C);
}
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];
        }
        dp[N+1]=0;
        for(int i=N;i>=1;i--) {
            dp[i]=inf;
            int su=0;
            int id=i-1;
            for(int j=0;;j++) {
                int la=id;
                while(id<N&&su+a[id+1]<=j*K&&id<la+M) id++,su+=a[id];
                if(id-la>=M) {
                    dp[i]=std::min(dp[i],dp[la+M+1]+j*C*K-su*C);
                    break;
                }
                if(id==N) {
                    dp[i]=std::min(dp[i],j*C*K-su*C);
                    break;
                }
                dp[i]=std::min(dp[i],dp[id+2]+fx(a[id+1]-(j*K-su)));
            }
        }
        printf("%lld\n",(long long)(dp[1]+ans*C)/K);
    }
}