#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];
ll dp[5005][5005];
#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;
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]%k,i),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=[&](const auto&x,const auto&v){return lower_bound(x.begin(),x.end(),v)-x.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--){
        int x=sum[i+m-1]-k+1;
        int r=(x%k+k)%k;
        rt[i+1]=A.query(1,1,tt,lb(tmp,sum[i]%k));
        if(x<sum[i]){
            int xx=(sum[i]+k-1)%k,w=lb(tmp,xx+1)-1;
            if(r<=xx) A.modify(1,1,tt,lb(tmp,r),w,i+m);
            else A.modify(1,1,tt,lb(tmp,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=0;i<=n+1;i++)
    for(int j=0;j<=n+1;j++) dp[i][j]=1e18;
    dp[1][1]=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++){
        chk(dp[i+1][i+1],dp[i][j]+cal(sum[i]-sum[j-1]));
        if(rt[j]>i+1) chk(dp[i+1][j],dp[i][j]);
    }
    cout<<dp[n+1][n+1]<<'\n';
}
int main(){
    int T;cin>>T;
    while(T--) solve();   
}