#include <cstdio>
#include <cassert>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5000 + 10;
const long long INF = 100000000000LL + 10;

int totN;
int n, k, d, m;
long long a[N + N], pre[N + N];
long long f[N][N];
pair<int, long long> que[N];
int qt, qh;

void solve()
{
	cin >> n >> k >> d >> m;
	assert(1 <= k && k < n && n <= 5000);
	assert(1 <= d && d < n && n <= 5000);
	assert(1 <= m && m <= 1000);
	totN += n;
	for(int i = 1; i <= n; ++ i) {
		cin >> a[i];
		assert(1 <= a[i] && a[i] <= 1000);
	}
	for(int i = n + 1; i <= n + n; ++ i) {
		a[i] = 0;
	}
	for(int i = 1; i <= n + n; ++ i) {
		pre[i] = pre[i - 1] + a[i];
	}

	for(int i = 0; i <= n; ++ i) {
		for(int j = 0; j <= k; ++ j) {
			f[i][j] = -INF;
		}
	}

	for(int i = 1; i <= n; ++ i) {
		f[i][1] = pre[i - 1] + (pre[i + d] - pre[i]) * m;
	}
	for(int j = 2; j <= k; ++ j) {
		{
			long long maxV = -INF;
			for(int i = 1; i <= n; ++ i) {
				if (i - d - 1 >= 0) {
					maxV = max(maxV, f[i - d - 1][j - 1] - pre[i - 1]);
				}
				f[i][j] = max(f[i][j], maxV + pre[i - 1] + (pre[i + d] - pre[i]) * m);
			}
		}
		{
			qh = qt = 0;
			for(int i = 1; i <= n; ++ i) {
				for( ; qh < qt; ) {
					if (que[qh].first + d < i) qh ++;
					else break;
				}
				if (qh < qt) {
					f[i][j] = max(f[i][j], que[qh].second + pre[i - 1] * m + (pre[i + d] - pre[i]) * m);
				}
				long long value = f[i][j - 1] - pre[i + d] * m;
				for( ; qh < qt; ) {
					if (que[qt - 1].second <= value) qt --;
					else break;
				}
				que[qt ++] = make_pair(i, value);
			}
		}
	}
	long long ret = 0;
	for(int i = 1; i <= n; ++ i) {
		long long value = f[i][k];
		if (i + d < n) {
			value += pre[n] - pre[i + d];
		}
		ret = max(ret, value);
	}
	cout << ret << endl;
}

int main()
{
	int q; cin >> q;
	assert(1 <= q && q <= 200);
	totN = 0;
	for( ; q --; ) {
		solve();
	}
	assert(1 <= totN && totN <= 5000);
	return 0;
}