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

// #define DEBUG

int solve(int s,int k,vector<pair<int,int>> const &machine){
  vector<int> most(s+1);
  for (auto const &m: machine){
#if DEBUG
    cerr<<"  machine  "<<m.first<<" -> "<<m.second<<endl;
#endif
    for (int i=s; i>=m.first; i--){
      int remain=i-m.first;
      int value=most[i]+m.second;
      if (remain+value<=k){
        most[remain]=max(most[remain],value);
      }

      if (i>0){
        most[i-1]=max(most[i-1],most[i]);
      }
    }
#if DEBUG
    cerr<<"  "; for (int z=0; z<=s; z++) cerr<<" "<<most[z]; cerr<<endl;
#endif
  }
  return most[0];
}

int main(){
  int n,m; cin>>n>>m;
  int s,k; cin>>s>>k;

  vector<vector<pair<int,int>>> machine(n);
  for (int i=0; i<m; i++){
    int x,a,b; cin>>x>>a>>b;
    machine[x-1].emplace_back(a,b);
  }

  for (int i=0; i+1<n; i++){
    // Steps that compress the list most should run first to give the most working space.
    sort(machine[i].begin(),machine[i].end(),[](pair<int,int> const &a,pair<int,int> const &b){
      return (a.second-a.first)<(b.second-b.first);
    });
    s=solve(s,k,machine[i]);
#if DEBUG
    cerr<<"  have "<<s<<endl;
#endif
  }
  cout<<s<<endl;
}