#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 , long long> f[N];
long long g[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];
	}
	int A , B;
	g[1] = a[1] / k * c + a[1] % k , f[1][a[1] % k] = a[1] / k * c + c;
	for (int i = 1;i <= n;i ++)
	{
		A = a[i + 1] / k * c , B = a[i + 1] % k;
		Min (g[i + 1] , g[i] + A + B);
		Min (f[i + 1][B] , g[i] + A + c);
		for (auto it : f[i])
		{
			long long x = it.first , y = it.second;
			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];
			A = nxt / k * c , B = nxt % k;
			Min (g[r + 1] , y + A + B);
			Min (f[r + 1][B] , y + A + c);
		}
		g[i] = 0 , f[i].clear ();
	}
	cout << g[n + 1] << '\n';
	g[n + 1] = 0 , f[n + 1].clear ();
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:30:29: error: cannot bind non-const lvalue reference of type ‘int&’ to a value of type ‘long long int’
   30 |                 Min (g[i + 1] , g[i] + A + B);
      |                      ~~~~~~~^
answer.code:7:16: note:   initializing argument 1 of ‘void Min(int&, int)’
    7 | void Min (int &x , int y)
      |           ~~~~~^
answer.code:31:21: error: cannot bind non-const lvalue reference of type ‘int&’ to a value of type ‘std::unordered_map<int, long long int>::mapped_type’ {aka ‘long long int’}
   31 |                 Min (f[i + 1][B] , g[i] + A + c);
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:7:16: note:   initializing argument 1 of ‘void Min(int&, int)’
    7 | void Min (int &x , int y)
      |           ~~~~~^
answer.code:45:37: error: cannot bind non-const lvalue reference of type ‘int&’ to a value of type ‘long long int’
   45 |                         Min (g[r + 1] , y + A + B);
      |                              ~~~~~~~^
answer.code:7:16: note:   initializing argument 1 of ‘void Min(int&, int)’
    7 | void Min (int &x , int y)
      |           ~~~~~^
answer.code:46:29: error: cannot bind non-const lvalue reference of type ‘int&’ to a value of type ‘std::unordered_map<int, long long int>::mapped_type’ {aka ‘long long int’}
   46 |                         Min (f[r + 1][B] , y + A + c);
      |                         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:7:16: note:   initializing argument 1 of ‘void Min(int&, int)’
    7 | void Min (int &x , int y)
      |           ~~~~~^