#include<bits/stdc++.h>
# define int long long
# define rep(i, j, k) for (int i = j; i <= k; ++i)
# define N 500005
# define inf 10000000000000000LL
using namespace std;

int T, n, m, k, c, a[N], pre[N], dp[5005][5005], ans;
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--)
	{
		ans = inf;
		cin >> n >> m >> k >> c;
		rep(i, 1, n) cin >> a[i];
		if (c == 1)
		{
			int cnt = 0;
			rep(i, 1, n)
			{
				cnt += a[i] / k, a[i] %= k;
				if (!a[i]) continue;
				++cnt;
				int now = k;
				rep(j, i, min(i + m - 1, n))
				{
					if (!now) break;
					int x = min(a[j], now); a[j] -= x, now -= x;
				}
			}
			cout << cnt << '\n';
			continue;
		}
		rep(i, 1, n) pre[i] = pre[i - 1] + a[i];
		rep(i, 1, n + 1) rep(j, 1, n + 1) dp[i][j] = inf;
		dp[1][1] = 0;
		rep(i, 1, n) rep(j, 1, i)
		{
			if (dp[i][j] == inf) continue;
			int num = (pre[i - 1] - pre[j - 1] + k - 1) / k, ex = num * k - pre[i - 1] + pre[j - 1], llt = (a[i] - ex) / k, ppt = a[i] - ex - llt * k;
			dp[i + 1][i + 1] = min(dp[i + 1][i + 1], dp[i][j] + llt * c + ppt);
			int pos = upper_bound(pre + 1, pre + n + 1, pre[i] - ppt + k) - pre - 1;
			if (pos >= i + m - 1) dp[i + m][i + m] = min(dp[i + m][i + m], dp[i][j] + (llt + 1) * c);
			else dp[pos + 1][i] = min(dp[pos + 1][i], dp[i][j] + (llt + 1) * c);
		}
		rep(i, 1, n + 1) ans = min(ans, dp[n + 1][i]);
		cout << ans << '\n';
	}
	return 0;
}