玄关 f[j][i] 表示第j-i天全打卡求调

/*

*/
#include<bits/stdc++.h>
#define INF 1000000000000005
#define maxn 100005
#define maxm maxn - 5
#define int long long
typedef long long ll;
using namespace std;
struct segmentree{
	int b[4000005], tag[4000005];
	void pushup(int p){
		b[p] = max(b[p * 2], b[p * 2 + 1]);
	}
	void build(int l, int r, int p){
		if(l == r){
			b[p] = 0;
			return;
		}
		int mid = l + (r - l) / 2;
		build(l, mid, p * 2);
		build(mid + 1, r, p * 2 + 1);
		pushup(p);
	}
	void pushdown(int l, int r, int p, int mid){
		if(!tag[p])return;
		b[p * 2] += tag[p];
		b[p * 2 + 1] += tag[p];
		tag[p * 2] += tag[p];
		tag[p * 2 + 1] += tag[p];
		tag[p] = 0;
	}
	void update(int l, int r, int p, int x, int y, int z){
		if(x <= l && r <= y){
			b[p] += z;
			tag[p] += z;
			return;
		}
		int mid = l + (r - l) / 2;
		pushdown(l, r, p, mid);
		if(x <= mid)update(l, mid, p * 2, x, y, z);
		if(y > mid)update(mid + 1, r, p * 2 + 1, x, y, z);
		pushup(p);
	}
} tr;
int C, T, n, m, k, d, num;
struct cha{
	//challenges
	int l, r, v;
}c[maxn];
int dis[maxn];
vector<int> reg[maxn];

//imaginery f[i][j] = we ran contiguously from day j to day i
signed main(){
	cin>>C>>T;
	while(T--){
		cin>>n>>m>>k>>d;
		num = 0;
		num++;
		dis[num] = 1;
		for(int i = 1; i <= m; i++){
			int x;
			cin>>c[i].r>>x>>c[i].v;
			c[i].l = c[i].r - x + 1;
			num++;
			dis[num] = c[i].r;
			num++;
			dis[num] = c[i].l;
		}
		sort(dis + 1, dis + num + 1);
		num = unique(dis + 1, dis + num + 1) - dis - 1;
		
		num = n;
		for(int i = 1; i <= num; i++)dis[i] = i;
		//no discretizing first
		
		for(int i = 1; i <= num; i++){
			while(!reg[i].empty())reg[i].pop_back();//cuz multi test cases
		}
		for(int i = 1; i <= m; i++){
			int now = lower_bound(dis + 1, dis + num + 1, c[i].r) - dis;
			reg[c[i].r].push_back(i);
		}
		tr.build(1, num, 1);
		int ans = 0, ansg = 0;
		//ansg = ans with a gap, cuz for f[i][i] we cant transfer from f[i - 1] we could risk 
		//having more than k contiguous so we need to leave a gap, thus ansg is the ans from last round
		
		int pt = 1;
		for(int i = 1; i <= num; i++){
//			cout<<ans<<endl;
			tr.update(1, num, 1, 1, i, -d);
			//we all run on day i so all -d
			
			tr.update(1, num, 1, i, i, ansg);
			//we continuously ran for day i to i, so we can transfer from any f[x][y] thats
			//at least a gap of 1 away from i
			ansg = ans;

			while(dis[i] - dis[pt] >= k){
//				cout<<" "<<pt<<endl;
				tr.update(1, num, 1, pt, pt, LLONG_MIN);
				//added by long long min basically turns it to 0 and it wont matter
				//to later calculations anymore
				pt++;
			}
			
			for(auto j: reg[i]){
				//all challenges ending on day i - 1, since we ran on i - 1 but not i
				int pos = c[j].l;//lower_bound(dis + 1, dis + i + 1, c[j].l) - dis;//amortized still nlogn
//				cout<<pos<<endl;
				//if the last time we didnt run was pos or earlier than we had at least c[j].y days
				//of continuous running up to day i and we can get the c[j].v
				if(pos < pt)continue;
//				cout<<j<<" "<<c[j].l<<" "<<c[j].r<<" "<<pos<<endl;
				
				tr.update(1, num, 1, pt, pos, c[j].v);
			}
		
			ans = max(ans, tr.b[1]);
		}
		cout<<ans<<endl;
	}
	return 0;
}