Rank是离散化天数用的，day[i]是离散化后存的任务以第i天为终点的任务

#include<bits/stdc++.h>
using namespace std;
using lll = __int128;
using ll = long long;
namespace Mashiro {
    char buf[1<<18],*p1=buf,*p2=buf;
    inline int getc() {
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++;
    }
    template<typename T>inline void read(T& x) {
        x=0;int f=1;
        char ch=getc();
        while(!isdigit(ch)){if(ch=='-')f=~f+1;ch=getc();}
        while (isdigit (ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getc();}
        x*=f;
    }
    template <typename T,typename... Args> inline void read(T& x, Args&... args) {
        read(x);
        read(args...);
    }
    char buffer[1<<18];int p11=-1;const int p22=(1<<18)-1;
    inline void flush() {fwrite(buffer,1,p11+1,stdout),p11=-1;}
    inline void putc(const char &x) {if (p11==p22) flush();buffer[++p11]=x;}
    template<typename T>inline void write(T x) {
        static int buf[40],top=0;
        if(x<0)putc('-'),x=~x+1;
        while(x)buf[++top]=x%10,x/=10;
        if(top==0)buf[++top]=0;
        while (top) putc(buf[top--]^48);
        putc(' ');
        flush();
     }
     template <typename T,typename... Args> inline void write(T x, Args... args) {
         write(x);
         write(args...);
     }
}
using namespace Mashiro;
namespace Misaka{//Debug
    auto seed=std::chrono::system_clock::now().time_since_epoch().count();
    std::mt19937 rnd(seed);
    template<typename T>T random(T l, T r) {// [-INTMAX,INTMAX]
    	return std::uniform_int_distribution<T>(l,r)(rnd); 
    }
    template<typename ItType>inline void Array_Print(ItType __first,ItType __end){
        for(ItType it=__first;it!=__end;++it)write(*it);
        putc('\n');
    }
    #define Time(T) while((double)clock()/CLOCKS_PER_SEC<T) 
    #define Pause cout<<endl;system("pause");
}
const int maxn=1e5+10;
struct SegT{
    struct node{
        ll add,maxx;
    }T[maxn<<2];
#define ls(u) u<<1
#define rs(u) u<<1|1
#define add(u) T[u].add
#define maxx(u) T[u].maxx
    inline void push_up(int u){
        maxx(u)=max(maxx(ls(u)),maxx(rs(u)));
    }
    inline void push_down(int u,int l,int r){
        if(add(u)==0)return;
        int mid=l+r>>1;
        add(ls(u))+=add(u);
        add(rs(u))+=add(u);
        maxx(ls(u))+=add(u);
        maxx(rs(u))+=add(u);
        add(u)=0;
    }
    void build(int k,int l,int r){
        if(l==r){
            maxx(k)=-1e18;
            return;
        }
        int mid=l+r>>1;
        build(ls(k),l,mid);
        build(rs(k),mid+1,r);
        push_up(k);
    }
    void modify(int k,int l,int r,int x,int y,ll v){
        if(x<=l&&r<=y){
            add(k)+=v;
            maxx(k)+=v;
            return;
        }
        int mid=l+r>>1;
        push_down(k,l,r);
        if(mid>=x)modify(ls(k),l,mid,x,y,v);
        if(mid<y)modify(rs(k),mid+1,r,x,y,v);
        push_up(k);
    }
    ll query(int k,int l,int r,int x,int y){
        if(l>r||y<l)return -1e18;
        if(x<=l&&r<=y)return maxx(k);
        int mid=l+r>>1;ll ans=-1e18;
        push_down(k,l,r);
        if(mid>=x)ans=query(ls(k),l,mid,x,y);
        if(mid<y)ans=max(ans,query(rs(k),mid+1,r,x,y));
        return ans;
    }
}Tree;
int C,T;
int n,m,k,d,md;
vector<int>Rank;
struct task{
    int x,y;
    ll v;
};
vector<task>Temp;
vector<task>day[maxn];
int main(){
    read(C,T);
    while(T--){
        read(n,m,k,d);
        Rank.clear();Temp.clear();
        Rank.emplace_back(0);
        for(int i(1),x,y,v;i<=m;++i){
            read(x,y,v);
            Temp.emplace_back(task{x,x-y+1,v});
            Rank.emplace_back(x);
        }
        sort(Rank.begin(),Rank.end());
        auto End=unique(Rank.begin(),Rank.end());
        md=End-Rank.begin();
        for(int i(1);i<=md;++i)day[i].clear();
        for(auto temp:Temp){
            int rk=lower_bound(Rank.begin(),End,temp.x,[](const int A,const int B){
                return A<B;
            })-Rank.begin()+1;
            day[rk].emplace_back(temp);
        }
        Tree.build(1,1,md);
        Tree.modify(1,1,md,1,1,1e18);
        ll ans=0;
        for(int i(2);i<=md;++i){
            int nxt=Rank[i-1]-Rank[i-2];
            Tree.modify(1,1,md,1,i-1,-nxt*1ll*d);
            for(auto temp:day[i]){
                int rk=lower_bound(Rank.begin(),End,temp.y,[](const int A,const int B){
                    return A<B;
                })-Rank.begin();
                Tree.modify(1,1,md,1,rk,temp.v);
            }
            int rk=lower_bound(Rank.begin(),End,Rank[i-1]-k,[](const int A,const int B){
                return A<B;
            })-Rank.begin();
            ll res=Tree.query(1,1,md,rk,i-1);
            //write(rk,res);puts("");
            Tree.modify(1,1,md,i,i,res);
            ans=max(ans,res);
        }
        write(ans);
        puts("");
    }
    return 0;
}