#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
int read(){int x=0;bool neg=0;char ch=gc();
    while(ch<'0'||ch>'9')neg|=(ch=='-'),ch=gc();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=gc();
    return neg?-x:x;
}//快读
#define ll long long
int n,m,k,c;
ll s[500005];//前缀和
struct P{//无旋treap
    int ls,rs,rd;ll key,G,tag;//key就是区间的值之和,G就是节省点费用
}v[500005];
int tot,rt;
inline void pushdown(int x){//加法标记
    if(!v[x].tag)return;
    v[v[x].ls].tag+=v[x].tag;
    v[v[x].rs].tag+=v[x].tag;
    v[x].key+=v[x].tag;
    v[x].tag=0;
}
int merge(int x,int y){//合并
    if(!x||!y)return x+y;
    if(v[x].rd>v[y].rd){
        pushdown(x);
        v[x].rs=merge(v[x].rs,y);
        return x;
    }
    pushdown(y);
    v[y].ls=merge(x,v[y].ls);
    return y;
}
void split(int x,int &y,int &z,int mid){//分裂为<mid 和 >=mid
    if(!x){y=z=0;return;}
    pushdown(x);
    if(v[x].key%k<mid){
        y=x;
        split(v[x].rs,v[x].rs,z,mid);
        return;
    }
    z=x;
    split(v[x].ls,y,v[x].ls,mid);
}
ll mx;//存储当区间全部清空时的节省的费用
ll bound_down(int x,ll lim){//暴力将大于上限的部分合并为上限,同时处理全部清空的节省费用
    if(!x)return 0;
    pushdown(x);
    mx=max(mx,v[x].G+v[x].key-(v[x].key/k+1)*c);
    v[x].G+=v[x].key/k*(k-c);
    v[x].key=lim;//修改为上限
    v[x].G=max(v[x].G,bound_down(v[x].ls,lim));//从儿子读取节省费用的最大值
    v[x].G=max(v[x].G,bound_down(v[x].rs,lim));
    v[x].ls=v[x].rs=0;//合并成一个点,不需要儿子
    return v[x].G;
}
void zero_up(int x,ll val){//添加或更新 key == 0 的情况
    int y=x;
    while(v[y].ls)y=v[y].ls;//一直向左
    if(v[y].key%k){//如果没有0,就添加一个
        v[++tot]=(P){0,0,rand(),0,val,0};
        rt=merge(tot,rt);
    }else v[y].G=max(val,v[y].G+v[y].key/k*(k-c)),v[y].key=0;//否则取max
}
void print(int x){//调试语句
    if(!x)return;
    pushdown(x);
    print(v[x].ls);
    v[x].G+=v[x].key/k*(k-c);
    v[x].key%=k;
    printf("(%lld %lld) ",v[x].G,v[x].key);
    print(v[x].rs);
}
void output(){//调试语句
    print(rt);
    printf("\n");
}
int main(){//freopen("in","r",stdin);
    int T=read(),i,j;
    while(T--){
        n=read();m=read();k=read();c=read();
        for(i=1;i<=n;i++)s[i]=s[i-1]+read();//读取前缀和
        tot=rt=1;
        v[1]=(P){0,0,rand(),s[m],0,0};//初始化
        for(i=m+1;i<=n;i++){//output();
            split(rt,rt,j,s[i-1]-s[i-m]);//取出超过上限的部分
            if(j){//如果有超出上限的部分
                mx=0;//用来存储当区间全部清空时的节省的费用
                bound_down(j,s[i-1]-s[i-m]);//合并超出上限的部分
                rt=merge(rt,j);//还原回去
                if(mx)zero_up(rt,mx);//更新 key == 0 的情况
            }
            int a=s[i]-s[i-1];//添加新的数
            split(rt,rt,j,k-(a-1)%k-1);
            v[rt].tag+=a;//加法标记
            v[j].tag+=a;
            rt=merge(j,rt);//调换顺序
        }//output();
        mx=0;
        bound_down(rt,0);//发现计算结果恰好跟合并上限的做法一样,就用了同一个函数
        printf("%lld\n",s[n]-max(mx,v[rt].G));//输出答案,然后wa了
        if(s[n]-max(mx,v[rt].G)==3370){
            printf("%d %d %d %d, ",n,m,k,c);
            for(i=1;i<=n;i++)printf("%d ",s[i]-s[i-1]);
            printf("\n");
        }
    }
    return 0;
}