挺震撼为啥能大数据过了但是小数据没过。

求调qwq

// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast", "inline", "-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; 
#define int LL
const int maxm = 1e5 + 10;
int T, n, m, k, d, f[maxm << 1];
struct chal {
    int l, r, v;
} c[maxm];
struct Node {
    int mx, ad;
} t[maxm << 3];
inline void pd(int u, int l, int r) {
    if(t[u].ad) {
        int mid = l + r >> 1;
        Node& rt = t[u], &ls = t[u << 1], &rs = t[u << 1 | 1];
        ls.ad += rt.ad, rs.ad += rt.ad;
        ls.mx += rt.ad, rs.mx += rt.ad;
        rt.ad = 0;
    }
}
inline void pu(int u) { t[u].mx = max(t[u << 1].mx, t[u << 1 | 1].mx); } 
inline void upd(int u, int L, int R, int l, int r, int k) {
    if(L > R) return ;
    // cout << L << ' ' << R  << ' ' << k << '\n';
    if(L <= l && r <= R) {
        t[u].ad += k, t[u].mx += k;
        return ;
    }
    pd(u, l, r);
    int mid = l + r >> 1;
    if(L <= mid) upd(u << 1, L, R, l, mid, k);
    if(R > mid) upd(u << 1 | 1, L, R, mid + 1, r, k);
    pu(u);
}
inline int Q(int u, int L, int R, int l, int r) {
    if(L > R) return 0;
    if(L <= l && r <= R) return t[u].mx;
    pd(u, l, r);
    int mid = l + r >> 1, mx = 0;
    if(L <= mid) mx = Q(u << 1, L, R, l, mid);
    if(R > mid) mx = max(Q(u << 1 | 1, L, R, mid + 1, r), mx);
    pu(u);
    return mx;
}
int p[maxm << 1], M;
inline void clear() {
    memset(t, 0, sizeof t);
    memset(f, 0, sizeof f);
}
inline void solve() {
    clear();
    cin >> n >> m >> k >> d;
    // cout << "seg  " << '\n'; 
    for(int l, r, x, y, v, i = 1; i <= m; ++ i) {
        cin >> x >> y >> v;
        l = x - y + 1, r = x;
        // cout << l  << ' ' << r << '\n';
        p[(i << 1) - 1] = l;
        p[i << 1] = r;
        c[i] = {l, r, v};
    }
    p[m + m + 1] = 0;
    sort(p + 1, p + 2 + m + m);
    M = unique(p + 1, p + 2 + m + m) - p - 1;
    // for(int i = 1; i <= M; ++ i) cout << p[i] << ' '; cout << '\n';
    for(int i = 1; i <= m; ++ i) {
        c[i].l = lower_bound(p + 1, p + 1 + M, c[i].l) - p;
        c[i].r = lower_bound(p + 1, p + 1 + M, c[i].r) - p;
    }
    sort(c + 1, c + 1 + m, [&](const chal& x, const chal& y) { return x.r < y.r; });
    int j = 1;
    // cout << '\n';
    for(int i = 1; i <= M; ++ i) {
        upd(1, 1, i - 1, 1, M, -d * (p[i] - p[i - 1])); 
        while(j <= m && c[j].r <= i) upd(1, 1, c[j].l, 1, M, c[j].v), j ++ ;
        int sl = lower_bound(p + 1, p + 1 + M, p[i] - k + 1) - p; 
        sl = max(sl, 1LL);
        // cout << i << " [" << sl << ", " << i - 1 << "]\n";
        f[i] = max(f[i - 1], Q(1, sl, i - 1, 1, M) - d);
        upd(1, i, i, 1, M, f[i - 1]);
    }
    // for(int i = 1; i <= M; ++ i) cout << f[i] << ' '; cout << '\n';
    cout << f[M] << '\n';
}
signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    cin >> T;
    while(T -- ) solve();
    return 0; 
}