#include<bits/stdc++.h> using namespace std; #define int long long int n , D; struct Station{ int x ,a , b; }; vector<Station> w; bool cmp(Station& a , Station& b){ return a.b > b.b; } bool cmp1(Station&a , Station& b){ return a.x < b.x; } struct Segtree{ vector<int> s , lz; int sz = 1; void init(int n){ while(sz < n)sz*=2; s.resize(sz*2 , -1); lz.resize(2*sz); } void build(vector<int>& v){ for(int i = 0 ;i <= n; i++)s[sz+i] = v[i]; for(int i =sz-1; i>= 1 ; i--) s[i] = max(s[2*i] , s[2*i+1]); } void apply(int node , int val){ s[node] += val; lz[node]+=val; } void push(int node){ if(lz[node] != 0){ apply(node*2 , lz[node]); apply(node*2+1 , lz[node]); lz[node] = 0; } } void pull(int node){ s[node] = max(s[node*2] , s[node*2+1]); } void range_add(int lq ,int rq , int val , int l , int r , int node){ if(rq < l || lq > r)return; if(lq <= l && r <= rq){ apply(node , val); return; } push(node); int mid = (l + r) / 2; range_add(lq , rq , val , l , mid , node*2); range_add(lq , rq , val , mid+1 , r , node*2+1); pull(node); } void range_add(int l , int r ,int val){ if(l > r)return; range_add(l , r , val , 0 , sz-1 , 1); } int query(){ return s[1]; } }; signed main(){ ios::sync_with_stdio(0); cin.tie(0) , cout.tie(0); cin>>n>>D; w.resize(n); for(int i = 0 ; i < n ;i++){ cin>>w[i].x>>w[i].a>>w[i].b; } int m = n + 1; Segtree st; st.init(m); vector<int> v(m); vector<Station> byB = w , byX = w; byB.push_back({D , 0 , LLONG_MAX/4}); sort(byB.begin() , byB.end() , cmp); byX.push_back({D , 0 , LLONG_MAX / 4}); sort(byX.begin() , byX.end() , cmp1); for(int i = 0 ; i< m ; i++){ v[i] = byX[i].x; } st.build(v); map<int , int> mp; for(int i = 0 ; i <= n; i++){ mp[byX[i].x] = i; } int ans = D; for(int i = 0 ;i<= n ;i++){ int t= byB[i].b; int idx = mp[byB[i].x]; st.range_add(idx +1, n , -byB[i].a); // st.range_add() int temp = max(0LL , st.query()); if(temp <= t){ ans = min(ans , temp); } } cout<<ans; }