#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+5;
int n,m,k,c;
int a[N];
typedef long long ll;
ll sum[N];
int rt[N];
#define ls p<<1
#define rs p<<1|1
constexpr int inf=1e9;
struct seg{
    int t[N<<2],g[N<<2];
    inline void app(int p,int k){t[p]=min(t[p],k),g[p]=min(g[p],k);}
    inline void pd(int p){if(g[p]<inf)app(ls,g[p]),app(rs,g[p]),g[p]=inf;}
    void build(int p,int l,int r){
        t[p]=g[p]=inf;
        if(l==r) return;
        int mid=l+r>>1;
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void modify(int p,int l,int r,int ql,int qr,int k){
        if(ql>qr) return;
        if(ql<=l&&r<=qr) return app(p,k);
        int mid=l+r>>1;pd(p);
        if(ql<=mid) modify(ls,l,mid,ql,qr,k);
        if(qr>mid) modify(rs,mid+1,r,ql,qr,k);
    }
    int query(int p,int l,int r,int k){
        if(l==r) return t[p];
        int mid=l+r>>1;pd(p);
        return k<=mid?query(ls,l,mid,k):query(rs,mid+1,r,k);
    }
}A;
constexpr ll Inf=1e18;
struct _seg{
    ll t[N<<2],_t[N<<2];
    inline void pu(int p){t[p]=min(t[ls],t[rs]);_t[p]=min(_t[ls],_t[rs]);}
    void build(int p,int l,int r){
        t[p]=_t[p]=Inf;
        if(l==r) return;
        int mid=l+r>>1;
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void assign(int p,int l,int r,int k,ll x,ll _x){
        // if(p==1) cout<<"assign "<<k<<' '<<x<<' '<<_x<<'\n';
        if(l==r) return t[p]=x,_t[p]=_x,void();
        int mid=l+r>>1;
        if(k<=mid) assign(ls,l,mid,k,x,_x);
        else assign(rs,mid+1,r,k,x,_x);
        pu(p);
    }
    ll query(int p,int l,int r,int ql,int qr,bool typ){
        if(ql<=l&&r<=qr) return (typ?_t:t)[p];
        int mid=l+r>>1;ll res=Inf;
        if(ql<=mid) res=query(ls,l,mid,ql,qr,typ);
        if(qr>mid) res=min(res,query(rs,mid+1,r,ql,qr,typ));
        return res;
    }
}B;
inline ll Q(int l,int r,bool typ){
    ll res=l>r?Inf:B.query(1,1,n,l,r,typ);
    // cout<<"query "<<l<<' '<<r<<' '<<typ<<": "<<res<<'\n';
    return res;
}
int id[N];
vector<int> L[N];
inline void solve(){
    cin>>n>>m>>k>>c;
    vector<pair<int,int>> v;
    vector<int> tmp;
    for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i],v.emplace_back(sum[i-1]%k,i-1),tmp.emplace_back(sum[i]%k);
    tmp.emplace_back(0);
    sort(tmp.begin(),tmp.end());tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    sort(v.begin(),v.end());
    int tt=tmp.size();
    auto lb=[&](int v){return lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin()+1;};
    auto sb=[&](pair<int,int> w){return lower_bound(v.begin(),v.end(),w)-v.begin()+1;};
    if(k<=c) return cout<<sum[n]<<'\n',void();
    auto cal=[&](ll x){return x/k*c+min<ll>(x%k,c);};
    auto chk=[&](auto&x,auto y){(x>y)&&(x=y);};
    memset(rt,0x3f,sizeof(*rt)*(n+1));
    A.build(1,1,tt);
    for(int i=n-m+1;i>=0;i--){
        ll x=sum[i+m-1]-k+1;
        int r=(x%k+k)%k;
        rt[i+1]=A.query(1,1,tt,lb(sum[i]%k));
        if(x<sum[i]){
            int xx=(sum[i]+k-1)%k,w=lb(xx+1)-1;
            if(r<=xx) A.modify(1,1,tt,lb(r),w,i+m);
            else A.modify(1,1,tt,lb(r),tt,i+m),A.modify(1,1,tt,1,w,i+m);
        }
    }
    // for(int i=1;i<=n;i++) cout<<rt[i]<<' ';cout<<'\n';
    for(int i=1;i<=n;i++) id[i]=sb({sum[i]%k,i}),L[i].clear();
    for(int i=1;i<=n;i++) if(rt[i]<=n) L[rt[i]-1].emplace_back(i);
    B.build(1,1,n);
    B.assign(1,1,n,sb({0,0}),0,0);
    // for(auto [x,y]:v) cout<<"{"<<x<<","<<y<<"} ";cout<<'\n';
    for(int i=1;i<=n;i++){
        for(int x:L[i]) B.assign(1,1,n,sb({sum[x-1]%k,x-1}),Inf,Inf);
        int p1=sb({sum[i]%k,0}),p2=sb({(sum[i]+k-c)%k,n+1});
        // cout<<sum[i]%k<<' '<<(sum[i]+k-c)%k<<' '<<p1<<' '<<p2<<'\n';
        ll res=0;
        if(p1<p2) res=min({Q(1,p1-1,1)+sum[i]%k,Q(p1,p2-1,0),Q(p2,n,1)-c+sum[i]%k+k});
        else res=min({Q(1,p2-1,0)+c,Q(p2,p1-1,1)+sum[i]%k,Q(p1,n,0)});
        // cout<<res+sum[i]/k*c<<'\n';
        if(i==n) cout<<res+sum[i]/k*c<<'\n';
        else B.assign(1,1,n,sb({sum[i]%k,i}),res,res-sum[i]%k);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;cin>>T;
    while(T--) solve();   
}