#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INFLL = (1LL<<60); struct Station { ll x; ll a; ll b; int idx; }; // comparator functions (no lambdas) bool cmpByX(const Station &s1, const Station &s2) { return s1.x < s2.x; } bool cmpByBDesc(const Station &s1, const Station &s2) { return s1.b > s2.b; } // Segment tree that supports range add and query global max struct SegTree { int n; // number of leaves (size) vector<ll> mx; // max values vector<ll> lazy; // lazy addition SegTree() : n(0) {} SegTree(int sz) { init(sz); } void init(int sz) { n = 1; while (n < sz) n <<= 1; mx.assign(2*n, -INFLL); lazy.assign(2*n, 0); } void build(const vector<ll> &arr) { // arr size <= n int m = (int)arr.size(); for (int i = 0; i < m; ++i) mx[n + i] = arr[i]; for (int i = m; i < n; ++i) mx[n + i] = -INFLL; for (int i = n - 1; i >= 1; --i) mx[i] = max(mx[2*i], mx[2*i+1]); } void apply(int node, ll val) { mx[node] += val; lazy[node] += val; } void push(int node) { if (lazy[node] != 0) { apply(2*node, lazy[node]); apply(2*node+1, lazy[node]); lazy[node] = 0; } } void pull(int node) { mx[node] = max(mx[2*node], mx[2*node+1]); } // add 'val' to range [l, r] inclusive void range_add(int l, int r, ll val) { if (l > r) return; range_add_rec(l, r, val, 1, 0, n-1); } void range_add_rec(int l, int r, ll val, int node, int nl, int nr) { if (r < nl || nr < l) return; if (l <= nl && nr <= r) { apply(node, val); return; } push(node); int mid = (nl + nr) >> 1; range_add_rec(l, r, val, 2*node, nl, mid); range_add_rec(l, r, val, 2*node+1, mid+1, nr); pull(node); } ll query_max() { return mx[1]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; ll D; if (!(cin >> N >> D)) return 0; vector<Station> st(N); for (int i = 0; i < N; ++i) { st[i].idx = i; cin >> st[i].x >> st[i].a >> st[i].b; } // sort stations by position x vector<Station> byPos = st; sort(byPos.begin(), byPos.end(), cmpByX); // build positions array: station positions then destination int m = N + 1; vector<ll> xs(m); for (int i = 0; i < N; ++i) xs[i] = byPos[i].x; xs[N] = D; // map original station index -> position index vector<int> posIndex(N); for (int i = 0; i < N; ++i) posIndex[ byPos[i].idx ] = i; // prepare vector of stations sorted by B descending vector<Station> byB = st; sort(byB.begin(), byB.end(), cmpByBDesc); // initial v[i] = x_i (pref = 0) vector<ll> v(m); for (int i = 0; i < m; ++i) v[i] = xs[i]; SegTree seg(m); seg.init(m); seg.build(v); ll ans = D; // empty-set candidate: no stations usable => need D fuel int idx = 0; while (idx < N) { ll curB = byB[idx].b; // process group of stations with the same B value int j = idx; while (j < N && byB[j].b == curB) { int origIdx = byB[j].idx; int p = posIndex[origIdx]; // position index in xs: 0..N-1 for stations ll A = byB[j].a; // when this station becomes usable, it reduces required fuel // for all checkpoints strictly after its position (i > p). seg.range_add(p+1, m-1, -A); ++j; } idx = j; ll g = seg.query_max(); if (g < 0) g = 0; // starting fuel can't be negative; 0 means no initial fuel required if (g <= curB) { if (g < ans) ans = g; } } cout << ans << '\n'; return 0; }