O(mklogm)做法，方法参考题解第1篇，全wa带t，求调

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long int64;

const int MAXM = 1e6 + 7;
const int64 INF = (1ll << 62ll) - 1ll + (1ll << 62ll);

struct task {
	int l, r;
	int64 val;
} b[MAXM];

int n, m, k;
int64 d;
int64 dp[MAXM];
vector<int> LSH_V;
vector<pair<int, int64> > a[MAXM];
unordered_map<int, int> LSH_M;

struct bitTree {
	int64 tree[MAXM]{};
	
	int lowbit(int x) {return x & (-x);}
	
	void add(int idx, int64 val) {
		idx = n - idx + 1;
		for(int i=idx; i<=n; i+=lowbit(i)) tree[i] += val;
	}
	
	int64 sum(int idx) {
		int64 res = 0;
		idx = n - idx + 1;
		for(int i=idx; i>=1; i-=lowbit(i)) res += tree[i];
		return res;
	}
} t;

template<typename T_int>
void input(T_int &x) {
	char ch = getchar();
	T_int fu = 1;
	x = 0;
	while(!('0' <= ch && ch <= '9')) fu = (fu == -1) ? fu : (ch == '-' ? -1 : 1), ch = getchar();
	while('0' <= ch && ch <= '9') x = x * 10 + (ch - '0'), ch = getchar();
	x *= fu;
}

void solve() {
	input(n), input(m), input(k), input(d);
	LSH_V.push_back(-1);
	for(int i=1; i<=m; i++) {
		input(b[i].r), input(b[i].l), input(b[i].val);
		b[i].l = b[i].r - b[i].l + 1;
		LSH_V.push_back(b[i].l);
		LSH_V.push_back(b[i].r);
	}
	sort(LSH_V.begin(), LSH_V.end());
	LSH_V.erase(unique(LSH_V.begin(), LSH_V.end()), LSH_V.end());
	for(int i=0; i<(int)LSH_V.size(); i++) LSH_M[LSH_V[i]] = i + 1, LSH_V[i] = i;
	LSH_V[0] = -1;
	for(int i=1; i<=m; i++) a[LSH_M[b[i].r]].push_back(make_pair(LSH_M[b[i].l], b[i].val));
	for(int i=1; i<(int)LSH_V.size(); i++) {
		for(auto tmp : a[i]) t.add(tmp.first, tmp.second);
		dp[i] = max(dp[i], dp[i-1]);
		for(int j=i; j>=1&&LSH_V[i]-LSH_V[j]+1<=k; j--) dp[i] = max(dp[i], dp[max(0, LSH_V[j-1] != LSH_V[j]-1 ? j-1 : j-2)] + t.sum(j) - d * (LSH_V[i] - LSH_V[j] + 1));
	}
	
	printf("%lld\n", dp[(int)LSH_V.size()-1]);
	for(int i=0; i<(int)LSH_V.size(); i++) a[i].clear(), dp[i] = 0, t.tree[i] = 0;
	memset(b, 0, sizeof b);
	LSH_V.clear();
	LSH_M.clear();
}

int main() {
//	freopen("a.in", "r", stdin);
	
	int c, T;
	input(c), input(T);
	while(T--) solve();
	
	return 0;
}