#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int n, m, k, c, a[N], s[N];
unordered_map <int, unordered_map <int, int> > f;
int dfs(int i, int x) {
	if (i > n) return 0;
	if (f[i].find(x) != f[i].end()) return f[i][x];
	if (!x) return dfs(i + 1, a[i + 1]);
	if (s[i + m - 1] - s[i] + x < k)
		return f[i][x] = min(dfs(i + 1, a[i + 1]) + x, dfs(i + m, a[i + m]) + c);
	if (x >= k) return f[i][x] = dfs(i, x % k) + x / k * c;
	int L = i, R = n, res = i;
	while (L <= R) {
		int mid = L + R >> 1;
		if (s[mid] - s[i] + x <= k) res = mid, L = mid + 1;
		else R = mid - 1;
	}
	return f[i][x] = dfs(res + 1, a[res + 1] - k + s[res] - s[i] + x) + c;
}
void solve() {
	cin >> n >> m >> k >> c; f.clear();
	for (int i = 1; i <= n; i++) 
		cin >> a[i], s[i] = s[i - 1] + a[i];
	cout << dfs(1, a[1]) << '\n';
}
signed main() {
	int T; cin >> T;
	while (T--) solve(); 
	return 0; 
}