#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];
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];
            su[i]=a[i]+su[i-1];
            ff[i]=su[i]-su[std::max(i-M+1,(__int128)0)];
        }
        for(int i=1;i<=N;i++) {
            rr[i]=N;
            for(int j=i;j<=N&&ff[j]<=K;j++) {
                if((su[j]-su[i-1])%K>ff[j]) {
                    rr[i]=j;
                    break;
                }
            }
        }
        dp[N+1]=0;
        for(int i=N;i>=1;i--) {
            dp[i]=inf;
            for(int j=i;j<=rr[i];j++) {
                dp[i]=std::min(dp[i],dp[j+1]+(su[j]-su[i-1])%K*(K-C));
            }
            int ss=su[rr[i]]-su[i-1];
            ss%=K;
            dp[i]=std::min(dp[i],dp[rr[i]+1]+C*(K-ss));
        }
        printf("%lld\n",(long long)((dp[1]+ans*C)/K));
    }
}