#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
ll dp[200010],s[200010];
int n,m,k;
ll d;
int cnt;
struct node{
    int x,y,v;
}a[100010];
bool operator<(node a,node b){
    return a.x<b.x;
}
struct treenode{
    ll val,tag;
    int l,r;
}tree[200010<<2];
void pushup(int u){
    tree[u].val=max(tree[u<<1].val,tree[u<<1|1].val);
    return;
}
void build(int u,int l,int r){
    tree[u].l=l,tree[u].r=r;
    tree[u].val=0;
    tree[u].tag=0;
    if(l==r){
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    return;
}
void change(int u,ll p){
    tree[u].tag+=p;
    tree[u].val+=p;
    return;
}
void pushdown(int u){
    change(u<<1,tree[u].tag);
    change(u<<1|1,tree[u].tag);
    tree[u].tag=0;
    return;
}
void modify(int u,int l,int r,int p){
    if(l<=tree[u].l&&tree[u].r<=r){
        change(u,p);
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid){
        modify(u<<1,l,r,p);
    }
    if(mid<r){
        modify(u<<1|1,l,r,p);
    }
    pushup(u);
    return;
}
ll query(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r){
        return tree[u].val;
    }
    ll ans=0;
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid){
        ans=max(ans,query(u<<1,l,r));
    }
    if(mid<r){
        ans=max(ans,query(u<<1|1,l,r));
    }
    return ans;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int c,t;
    cin>>c>>t;
    while(t--){
        cin>>n>>m>>k>>d;
        cnt=0;
        for(int i=1;i<=m;i++){
            cin>>a[i].x>>a[i].y>>a[i].v;
            s[++cnt]=a[i].x;
            s[++cnt]=a[i].x-a[i].y+1;
        }
        sort(s+1,s+cnt+1);
        cnt=unique(s+1,s+cnt+1)-s-1;
        build(1,1,cnt);
        sort(a+1,a+m+1);
        for(int i=0;i<=cnt;i++)dp[i]=0;
        int p=1;
        for(int i=1;i<=cnt;i++){
            while(p<=m&&a[p].x<s[i]){
                p++;
            }
            while(p<=m&&a[p].x==s[i]){
                int l=lower_bound(s+1,s+cnt+1,a[p].x-a[p].y+1)-s;
                modify(1,1,l,a[p].v);
                p++;
            }
            int j=lower_bound(s+1,s+cnt+1,s[i]-k+1)-s;
            if(j<i)dp[i]=max(dp[i],query(1,j,i-1)-(s[i]+1ll)*d);
            int p=i-2;
            if(s[i-1]!=s[i]-1){
                p=i-1;
            }
            int ps=0;
            if(p>=0)ps=dp[p];
            dp[i]=max(dp[i],ps-d+query(1,i,i));
            dp[i]=max(dp[i],dp[i-1]);
            modify(1,i,i,ps+s[i]*d);
        }
        cout<<dp[cnt]<<"\n";
    }
    return 0;
}