rt，我 NOIP T4 现在离散化是 $4m$ 的，有大佬能帮我搞到 $2m$ 吗，好像左开右闭和左闭右开都不太行 /kel

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXM = 4e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

struct node {
	int l, r; ll v;
	bool operator < (const node &rhs) const { return r == rhs.r ? l > rhs.l : r < rhs.r; }
} a[MAXN];

struct segt {
	int l, r; ll add, val;
} t[MAXM << 2];

inline 
void pushup(int p) {
	t[p].val = max(t[p << 1].val, t[p << 1 | 1].val);
}

inline 
void upd(int p, ll x) {
	t[p].add += x, t[p].val += x;
}

inline 
void pushdown(int p) {
	if (!t[p].add) return ;
	upd(p << 1, t[p].add), upd(p << 1 | 1, t[p].add), t[p].add = 0;
}

inline 
void build(int l, int r, int p) {
	t[p].l = l, t[p].r = r, t[p].add = t[p].val = 0;
	if (l == r) return ; int mid = l + r >> 1;
	build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

inline 
void modify(int k, ll x, int p) {
	if (t[p].l == t[p].r) return upd(p, x - t[p].val);
	pushdown(p); int mid = t[p].l + t[p].r >> 1;
	modify(k, x, p << 1 | k > mid), pushup(p);
}

inline 
void add(int l, int r, ll x, int p) {
	if (l <= t[p].l && t[p].r <= r) return upd(p, x);
	pushdown(p); int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) add(l, r, x, p << 1);
	if (r > mid) add(l, r, x, p << 1 | 1); pushup(p);
}

inline 
ll query(int l, int r, int p) {
	if (l <= t[p].l && t[p].r <= r) return t[p].val;
	pushdown(p); int mid = t[p].l + t[p].r >> 1; ll ans = -inf;
	if (l <= mid) ans = max(ans, query(l, r, p << 1));
	if (r > mid) ans = max(ans, query(l, r, p << 1 | 1)); return ans;
}

int b[MAXM], tot;

int c, T, n, m, p, k; ll x, d, ans;

int main() {
	freopen("run6.in", "r", stdin);
	for (scanf("%d%d", &c, &T); T--;) {
		scanf("%d%d%d%lld", &n, &m, &p, &d), tot = 0;
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%lld", &a[i].r, &a[i].l, &a[i].v);
			a[i].l = a[i].r - a[i].l + 1;
			b[++tot] = a[i].l, b[++tot] = a[i].r;
			b[++tot] = a[i].l - 1, b[++tot] = a[i].r + 1;
		}
		sort(b + 1, b + tot + 1), tot = unique(b + 1, b + tot + 1) - b - 1;
		for (int i = 1; i <= m; i++) {
			a[i].l = lower_bound(b + 1, b + tot + 1, a[i].l) - b;
			a[i].r = lower_bound(b + 1, b + tot + 1, a[i].r) - b;
		}
		sort(a + 1, a + m + 1), build(0, tot, 1);
		for (int i = 1, j = 1, k = 0; i <= tot; i++) {
			for (; b[i] - b[k] > p; k++);
			x = query(max(k - 1, 0), i - 1, 1);
			add(k, i - 1, -d * (b[i] - b[i - 1]), 1), modify(i, x, 1);
			if (k > 0) modify(k - 1, 0, 1);
			for (; j <= m && a[j].r < i; j++);
			for (; a[j].r == i; j++) add(k, a[j].l - 1, a[j].v, 1);
		}
		printf("%lld\n", query(0, tot, 1));
	}
}