#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int x,y,day;
}a[10005];
int v(int f,int l,int r,int n,int m,int k,int d){
    int sum;
    for(int i=1;i<=m;i++){
        if(f==a[i].day&&r==a[i].x)l+=a[i].y;
    }
    if(f==n)return l;
    if(r==k)sum=v(f+1,l,0,n,m,k,d);
    else sum=max(v(f+1,l,0,n,m,k,d),v(f+1,l-d,r+1,n,m,k,d));
    return sum;
}
signed main(){
	//freopen("run.in","r",stdin);
    //freopen("run.out","w",stdout);
	int c,t,n,m,k,d;
    cin>>c>>t;
    while(t--){
        cin>>n>>m>>k>>d;
        for(int i=1;i<=m;i++)cin>>a[i].day>>a[i].x>>a[i].y;
        cout<<v(0,0,0,n,m,k,d);
    }  
    return 0;
}