#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node {int l,r,v;} a[100001];
bool cmp(node x,node y) {return x.r < y.r;}
int b[200001];
long long cnt[200001],dp[200001];
int main()
{
    int c,t;
    scanf("%d%d",&c,&t);
    while(t--)
    {
    	memset(dp,0,sizeof(dp));
    	memset(cnt,0,sizeof(cnt));
    	int n,m,k,d,tmp,nn = 0;
    	scanf("%d%d%d%d",&n,&m,&k,&d);
    	for(int i = 1;i <= m;i++)
    	{
    		scanf("%d%d%d",&a[i].r,&tmp,&a[i].v);
    		a[i].l = a[i].r-tmp+1;
    		b[++nn] = a[i].l;
    		b[++nn] = a[i].r;
		}
		sort(b+1,b+1+nn);
		nn = unique(b+1,b+1+nn)-b-1;
		for(int i = 1;i <= m;i++)
		{
			a[i].l = lower_bound(b+1,b+1+nn,a[i].l)-b;
			a[i].r = lower_bound(b+1,b+1+nn,a[i].r)-b;
		}
		sort(a+1,a+1+m,cmp);
		int pt = 1;
		for(int i = 1;i <= nn;i++)
		{
			while(pt <= m && a[pt].r == i)
			{
				cnt[a[pt].l] += a[pt].v;
				pt++;
			}
			long long now = 0;
			for(int j = i;j >= 1 && b[i]-b[j]+1 <= k;j--)
			{
				now += cnt[j];
				if(b[j]-b[j-1] == 1) dp[i] = max(dp[i],dp[max(j-2,0)]+now-1ll*d*(b[i]-b[j]+1));
				else dp[i] = max(dp[i],dp[j-1]+now-1ll*d*(b[i]-b[j]+1));
			}
			dp[i] = max(dp[i],dp[i-1]);
		}
		printf("%lld\n",dp[nn]);
	}
    return 0;
}

这个做法没有加线段树，显然是 $O(n^2)$（这里的 $n$ 离散化了，变成了 $10^5$ 量级的），但是民间数据居然 AC 了，可见的民间数据一点都不强（没有特意卡常，正常应该是 $52$ 分的）