0pts求条玄关

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt=0;
int g[200010];
int dp[200010];
struct energy{
	int l,r,v;
};
vector<energy> egy;
bool cmp(energy x,energy y){
	return x.r<y.r;
}
int hy[200010];
map<int,int> ls;
struct tree{
	int lid,rid;
	int left,right;
	int lazy;
	int v;
}leaf[800010];
int build_tree(int l,int r){
	int id=++cnt;
	leaf[id].left=l,leaf[id].right=r;
	leaf[id].v=0,leaf[id].lazy=0;
	if(l==r)
		return id;
	int mid=(l+r)>>1;
	leaf[id].lid=build_tree(l,mid);
	leaf[id].rid=build_tree(mid+1,r);
	return id;
}
void update(int id){
	leaf[leaf[id].lid].v+=leaf[id].lazy;
	leaf[leaf[id].rid].v+=leaf[id].lazy;
	leaf[leaf[id].lid].lazy+=leaf[id].lazy;
	leaf[leaf[id].rid].lazy+=leaf[id].lazy;
	leaf[id].lazy=0;
	leaf[id].v=max(leaf[leaf[id].lid].v,leaf[leaf[id].rid].v);
	return;
}
void cover(int x,int v,int id){
	if(leaf[id].left==leaf[id].right){
		leaf[id].v=v;
		return;
	}
	update(id);
	int mid=(leaf[id].left+leaf[id].right)>>1;
	if(mid>=x)
		cover(x,v,leaf[id].lid);
	else
		cover(x,v,leaf[id].rid);
	leaf[id].v=max(leaf[leaf[id].lid].v,leaf[leaf[id].rid].v);
	return;
}
void add(int l,int r,int v,int id){
	update(id);
	if(l<=leaf[id].left and leaf[id].right<=r){
		leaf[id].lazy+=v;
		leaf[id].v+=v;
		return;
	}
	int mid=(leaf[id].left+leaf[id].right)>>1;
	if(mid>=l)
		add(l,r,v,leaf[id].lid);
	if(mid<r)
		add(l,r,v,leaf[id].rid);
	leaf[id].v=max(leaf[leaf[id].lid].v,leaf[leaf[id].rid].v);
	return ;
}
int read_tree(int l,int r,int id){
	int ans=0;
	if(leaf[id].left!=leaf[id].right)update(id);
	if(l<=leaf[id].left and leaf[id].right<=r)
		return leaf[id].v;
	int mid=(leaf[id].left+leaf[id].right)>>1;
	if(mid>=l)
		ans=max(ans,read_tree(l,r,leaf[id].lid));
	if(mid<r)
		ans=max(ans,read_tree(l,r,leaf[id].rid));
	return ans;
}
void work(){
	int n,m,d,k;
	int root;
	cin>>n>>m>>k>>d;
	n=0;
	for(int i=1;i<=m;i++){
		int l,r,v;
		cin>>l>>r>>v;
		ls[l]=1;
		ls[r]=1;
		egy.push_back({l,r,v});
	}sort(egy.begin(),egy.end(),cmp); 
	for(map<int,int>::iterator i=ls.begin();i!=ls.end();i++){
		++n;
		ls[i->first]=n;
		hy[n]=i->first;
	}
	for(int i=0;i<egy.size();++i)
		egy[i].l=ls[egy[i].l],egy[i].r=ls[egy[i].r];
	root=build_tree(1,n);
	for(int i=1,j=0;i<=n;i++){
		g[i]=max(g[i-1],dp[i-1]);
		cover(i,g[i]+hy[i]*d,root);
		int ik=ls.lower_bound(i-k)->second;
		while(egy[j].r<=i){
			if(egy[j].l-1>=ik)add(ik,egy[j].l-1,egy[j].v,root);
			++j;
		}
		if(ik<=i)dp[i]=read_tree(ik,i,root)-hy[i]*d;
	}
	cout<<max(g[n],dp[n])<<'\n';
	ls.clear();
	egy.clear();
	memset(g,0,sizeof g);
	memset(dp,0,sizeof dp);
	cnt=0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int c,t;
	cin>>c>>t;
	for(int i=1;i<=t;i++)
		work();
	return 0;
}