#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500009;
const int inf=1000009;
int n,m;
ll k,c,a[N],s[N];

#define ls tr[node].ln
#define rs tr[node].rn
#define mid ((l+r)>>1)
struct tree{
	int ln,rn;
	int lsmn,lsmx,tg;
	int val;
	tree(){ ln=rn=lsmn=lsmx=tg=val=0; }
}tr[N*60];
int rt,cntnode,to[N];
void pushdown(int node){
	if(!ls) ls=++cntnode;
	if(!rs) rs=++cntnode;
	if(tr[node].tg){
		tr[ls].lsmn=tr[ls].lsmx=tr[ls].tg=tr[node].tg;
		tr[rs].lsmn=tr[rs].lsmx=tr[rs].tg=tr[node].tg;
		tr[node].tg=0;
	}
	if(tr[node].val){
		tr[ls].val=tr[rs].val=tr[node].val;
		tr[node].val=0;
	}
	return;
}
void pushup(int node){
	tr[node].lsmn=min(tr[ls].lsmn,tr[rs].lsmn);
	tr[node].lsmx=max(tr[ls].lsmx,tr[rs].lsmx);
	return;
}
void updval(int node,int l,int r,int tarl,int tarr,int x){
	if(tarl<=l&&r<=tarr){
		if(tr[node].lsmn>=x+m){
			tr[node].val=x;
			return;
		}
		if(tr[node].lsmx<x+m) return;
		pushdown(node);
		if(tarl<=mid) updval(ls,l,mid,tarl,tarr,x);
		if(tarr>mid) updval(rs,mid+1,r,tarl,tarr,x);
		pushup(node);
		return;
	}
	pushdown(node);
	if(tarl<=mid) updval(ls,l,mid,tarl,tarr,x);
	if(tarr>mid) updval(rs,mid+1,r,tarl,tarr,x);
	pushup(node);
	return;
}
void updls(int node,int l,int r,int tarl,int tarr,int x){
	if(tarl<=l&&r<=tarr){
		tr[node].lsmn=tr[node].lsmx=tr[node].tg=x;
		return;
	}
	pushdown(node);
	if(tarl<=mid) updls(ls,l,mid,tarl,tarr,x);
	if(tarr>mid) updls(rs,mid+1,r,tarl,tarr,x);
	pushup(node);
	return;
}
void upd1(int id,ll l,ll r){
	if(r-l+1>=k) updval(rt,0,k-1,0,k-1,id);
	else{
		l%=k; r%=k;
		if(l<=r) updval(rt,0,k-1,l,r,id);
		else updval(rt,0,k-1,l,k-1,id),updval(rt,0,k-1,0,r,id);
	}
	return;
}
void upd2(int id,ll l,ll r){
	if(r-l+1>=k) updls(rt,0,k-1,0,k-1,id);
	else{
		l%=k; r%=k;
		if(l<=r) updls(rt,0,k-1,l,r,id);
		else updls(rt,0,k-1,l,k-1,id),updls(rt,0,k-1,0,r,id);
	}
	return;
}
int query(int node,int l,int r,int tar){
	if(tr[node].val) return tr[node].val;
	if(tar<=mid) return query(ls,l,mid,tar);
	else return query(rs,mid+1,r,tar);
}
void init(){
	rt=cntnode=1;
	tr[1].lsmn=tr[1].lsmx=tr[1].tg=tr[1].val=inf;
	for(int i=n;i>=1;i--){
		upd1(i,s[i-1]+1,s[i]);
		to[i]=query(rt,0,k-1,(s[i-1]+1)%k);
		to[i]=min(to[i],n);
		upd2(i,s[i-1]+2,s[i]+1);
	}
	return;
}

ll f[N];
void work(){
	ll sum;
	for(int i=n;i>=1;i--){
		f[i]=a[i]+f[i+1];
		for(int j=i;j<=to[i];j++){
			sum=s[j]-s[i-1];
			f[i]=min(f[i],f[j+1]+sum-sum/k*(k-c));
		}
	}
	cout<<f[1]<<'\n';
	return;
}
void clr(){
	for(int i=1;i<=cntnode;i++)
		tr[i].ln=tr[i].rn=tr[i].lsmn=tr[i].lsmx=tr[i].tg=tr[i].val=0;
	rt=cntnode=0;
	for(int i=1;i<=n;i++) f[i]=s[i]=0;
	return;
}
void solve(){
	cin>>n>>m>>k>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	if(k<=c){
		cout<<s[n]<<'\n';
		return;
	}
	init();
//	for(int i=1;i<=n;i++)
//		cout<<to[i]<<" ";
//	cout<<endl;
	work();
	clr();
	return;
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}