rt，云斗68pts，#1 #2 #6 #8 WA,#22-25 TLE（估计是评测机的问题）；洛谷100pts，求能hack的小样例

#include<bits/stdc++.h>
#define LL long long
#define pii pair <int,int>
using namespace std;
inline int read() {
    int f=1,s=0; char ch=getchar();
    while (ch<48 || ch>57) {if (ch=='-') f=-1; ch=getchar();}
    while (ch>=48 && ch<=57) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
    return s*f;
}
const int N=1e5+3;
int C,T,n,M,m,k,d,b[N<<1],sz,L,R;
LL dp[N<<1],tr[N<<3],tag[N<<3],trmax[N<<3],K;
struct tas {int l,r,v;} t[N];
map <int,int> mp;
bool cmp (tas t1,tas t2) {return t1.r<t2.r;}
#define lson (p<<1)
#define rson (p<<1|1)
#define mid ((l+r)>>1)
void pushdown(int p,int l,int r) {
    if (tag[p]) {
        tr[lson]+=tag[p]*(mid-l+1);
        tr[rson]+=tag[p]*(r-mid);
        trmax[lson]+=tag[p];
        trmax[rson]+=tag[p];
        tag[lson]+=tag[p];
        tag[rson]+=tag[p];
        tag[p]=0;
    }
}
void update(int p,int l,int r) {
    if (L<=l && r<=R)
    {tr[p]+=K*(r-l+1),tag[p]+=K,trmax[p]+=K; return ;}
    pushdown(p,l,r);
    if (L<=mid) update(lson,l,mid);
    if (R>mid) update(rson,mid+1,r);
    tr[p]=tr[lson]+tr[rson];
    trmax[p]=max(trmax[lson],trmax[rson]);
}
LL query(int p,int l,int r) {
    if (L<=l && r<=R) return tr[p];
    pushdown(p,l,r);
    LL res=0;
    if (L<=mid) res+=query(lson,l,mid);
    if (R>mid) res+=query(rson,mid+1,r);
    return res;
}
LL query_max(int p,int l,int r) {
    if (L<=l && r<=R) return trmax[p];
    pushdown(p,l,r);
    LL res=0;
    if (L<=mid) res=max(res,query_max(lson,l,mid));
    if (R>mid) res=max(res,query_max(rson,mid+1,r));
    return res;
}
int Find(int x) {
    int l=1,r=sz+1;
    while (l<r) {
        int Mid=(l+r)>>1;
        if (b[Mid]>=x) r=Mid;
        else l=Mid+1;
    }
    return l;
}
int main() {
    freopen("run.in","r",stdin);
    freopen("run.out","w",stdout);
    C=read(),T=read();
    while (T--) {
        n=read(),M=read(),k=read(),d=read();
        sz=0,m=0;
        while (M--) {
            int x=read(),y=read(),v=read();
            if (y>k) continue;
            t[++m]=(tas){x-y+1,x,v};
            b[++sz]=x-y+1,b[++sz]=x;
        }
        sort(b+1,b+sz+1);
        sz=unique(b+1,b+sz+1)-b-1;
        for (int i=1;i<=sz;++i) mp[b[i]]=i;
        sort(t+1,t+m+1,cmp);
        int pnt=1;
        memset(tr,0,sizeof(tr));
        memset(trmax,0,sizeof(trmax));
        memset(tag,0,sizeof(tag));
        memset(dp,0,sizeof(dp));
        for (int i=1;i<=sz;++i) {
            while (t[pnt].r==b[i]) {
                R=mp[t[pnt].l];
                L=Find(t[pnt].r-k+1);
                K=t[pnt].v;
                update(1,1,sz);
                ++pnt;
            }
            L=i,R=i;
            if (b[i]-b[i-1]==1) K=dp[max(i-2,0)]+(LL)d*b[i];
            else K=dp[i-1]+(LL)d*b[i];
            update(1,1,sz);
            L=Find(b[i]-k+1),R=i;
            dp[i]=max(dp[i-1],query_max(1,1,sz)-(LL)d*(b[i]+1));
        }
        printf("%lld\n",dp[sz]);
    }
    return 0;
}