#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;
#define upper 50000
int dp[upper+5],s[100005];
int main(){
    int T=read(),i,j;
    while(T--){
        n=read();m=read();k=read();c=read();
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)s[i]=s[i-1]+read();
        for(i=s[m]-1;i>=0;i--)
            dp[i]=min(dp[i+1]+1,dp[i+k]+c);
        for(i=k-1;i>=0;i--)
            dp[0]=min(dp[0],dp[i]+c);
        for(i=m+1;i<=n;i++){
            int p=s[i-1]-s[i-m];
            for(j=p+1;j<=upper;j++)
                dp[j]=dp[p];
            p=s[i]-s[i-1];
            for(j=upper;j>=p;j--)
                dp[j]=dp[j-p];
            for(j=p-1;j>=0;j--)
                dp[j]=min(dp[j+1]+1,dp[j+k]+c);
            for(j=k-1;j>=0;j--)
            dp[0]=min(dp[0],dp[j]+c);
        }
        printf("%d\n",dp[0]);
    }
    return 0;
}