#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n , m , k , c , a[N] , s[N] , ans;
unordered_map <int , int> f[2][N];
void Min (int &x , int y)
{
	if (x > y || x == 0)
		x = y;
}
signed main ()
{
	int t;
	cin >> t;
	while (t --)
	{
	cin >> n >> m >> k >> c;
	s[n + 1] = a[n + 1] = 0;
	for (int i = 1;i <= n;i ++)
	{
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	f[0][1][0] = a[1] / k * c + a[1] % k , f[1][1][a[1] % k] = a[1] / k * c + c;
	for (int i = 1;i <= n;i ++)
	{
		int y = f[0][i][0];
//			cout << "0 : "<< i << ' ' << y << endl;
		Min (f[0][i + 1][0] , y + a[i + 1] / k * c + a[i + 1] % k);
		Min (f[1][i + 1][a[i + 1] % k] , y + a[i + 1] / k * c + c);
		for (auto it : f[1][i])
		{
			int x = it.first , y = it.second;
//			cout << "1 : "<< i << ' ' << x << ' ' << y << endl;
			int tp = min (i + m - 1 , n) , p = k - x , l = i , r = tp , mid;
			while (l < r)
			{
				mid = l + r + 1 >> 1;
				if (s[mid] - s[i] <= p) l = mid;
				else r = mid - 1;
			}
			int nxt = a[r + 1] - p + s[r] - s[i];
			if (r == tp) nxt = a[r + 1];
//			cout << r + 1 << ' ' << nxt % k << ' ' << (nxt - 1) / k * c + c << endl;
			Min (f[0][r + 1][0] , y + nxt / k * c + nxt % k);
			Min (f[1][r + 1][nxt % k] , y + nxt / k * c + c);
		}
		f[0][i].clear () , f[1][i].clear ();
	}
	cout << f[0][n + 1][0] << '\n';
	f[0][n + 1].clear () , f[1][n + 1].clear ();
	}
	return 0;
}