#include<bits/stdc++.h>
using namespace std;

#define N 100010
#define int long long

struct tz{
  int x, y, v;
}a[N];

int c;
int n, m, k, d;
int vis[N];
int t1[N];
int cnt, ans;

void solve17_18(){
  cnt = 0;
  cin >> n >> m >> k >> d;
  for(int i = 1; i <= m; i ++){
    int x, y, z;
    cin >> x >> y >> z;
    if(y > k || x - y + 1 <= 0) continue;
    a[++cnt] = {x, y, z};
  }
  int ans = 0;
  for(int i = 1; i <= cnt; i ++){
    if(a[i].v > a[i].y * d){
      ans += a[i].v - a[i].y * d;
    }
  }
  cout << ans << endl;
}

void check(){
  int now = 0;
  int res = 0, tmp = 0;
  for(int i = 1; i <= n; i ++){
    if(vis[i]) {
      now++; tmp -= d;
    }
    else now = 0;
    for(int j = 1; j <= cnt;j ++){
      if(a[j].x > i) break;
      if(a[j].x == i && now >= a[j].y) tmp += a[j].v;
    }
    res = max(res, tmp);
  }
  ans = max(ans, res);
}

void dfs(int u, int nk){
  if(nk > k) return ;
  if(u == n + 1){
    check();
    return ;
  }
  vis[u] = 1;
  // for(int i = 1; i <= n; i ++) if(vis[i]) k++;
  // cout << k << endl;
  dfs(u + 1, nk + 1);
  vis[u] = 0;
  dfs(u + 1, nk);
}

int cmp(tz a, tz b) {return a.x < b.x;}

void solve1_2(){
  ans = 0;
  cnt = 0;
  cin >> n >> m >> k >> d;
  for(int i = 1; i <= m; i ++){
    int x, y, z;
    cin >> x >> y >> z;
    if(y > k || x - y + 1 <= 0) continue;
    a[++cnt] = {x, y, z};
  }
  sort(a + 1, a + cnt + 1, cmp);
  dfs(1, 0);
  cout << ans << endl;
}

signed main(){
  freopen("run5.in", "r", stdin);
  // freopen("run.out", "w", stdout);
  int TN;
  cin >> c >> TN;
  while(TN--){
    if(c == 1 || c == 2) solve1_2();
    if(c == 17 || c == 18) solve17_18();
  }
}

不知道为什么交到云斗上没分，自己测样例是过的，16ptsQAQ