#include <bits/stdc++.h>
#define LL long long
int T,N,M,K,C,a[1000009];
LL dp[1000009];
signed main(void) {
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d %d %d",&N,&M,&K,&C);
        LL ans=0;
        for(int i=1;i<=N;i++) {
            scanf("%d",&a[i]);
            ans+=a[i];
        }
        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;
            LL su=0;
            for(int i=p;i<p+M&&i<=N;i++) {
                su+=a[i];
            }
            if(su<K) {
                p++;
            } else {
                int le=K;
                for(int i=p;i<p+M&&i<=N;i++) {
                    LL tq=std::min(a[i],le);
                    le-=tq;a[i]-=tq;
                }
                ans-=(K-le)-C;
            }
        }
        for(int i=1;i<=N;i++) {
            dp[i]=dp[i-1];
            LL ss=0;
            for(int j=i;j>=i-M+1&&j>=1;j--) {
                ss+=a[j];
            }
            if(ss>C) dp[i]=std::max(dp[i],dp[std::max(i-M,0)]+ss-C);
        }
        printf("%lld\n",ans-dp[N]);
    }
}