#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(r) (int)(r).size()
#define all(r) (r).begin(), (r).end()
const int MOD = (int)1e9 + 7;
const int INF = (int)4e18 + 18;
void solve();
int32_t main() {
#define CODE "task"
if (fopen(CODE".inp", "r"))
freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
int testcases = 1;
#define multitest 0
if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
}
/** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/
/** The Last Dance **/
struct FUELSTATION {
int X, A, B;
bool operator < (const FUELSTATION &other) const {
return (X == other.X ? A < other.A : X < other.X);
}
};
int N, D;
vector <FUELSTATION> stations;
namespace sub1 {
bool check_condition() {
return N == 1;
}
void solve() {
cout << (max(stations[0].X, D - stations[0].A) <= stations[0].B ? max(stations[0].X, D - stations[0].A) : D) << '\n';
}
}
namespace sub2 {
bool check_condition() {
for (auto item : stations)
if (item.B != 1e9)
return 0;
return 1;
}
void solve() {
sort(all(stations));
int ans = 0;
int sum = 0;
for (int i = 0; i < sz(stations); ++i) {
ans = max(ans, stations[i].X - sum);
sum += stations[i].A;
}
ans = max(ans, D - sum);
cout << ans << '\n';
}
}
namespace sub356 {
bool check_condition() {
return N <= 1e4;
}
bool possible(int f) {
int F = f;
for (int i = 1; i < sz(stations); ++i) {
f -= stations[i].X - stations[i - 1].X;
if (f < 0)
return 0;
if (F > stations[i].B)
continue;
f += stations[i].A;
}
return 1;
}
void solve() {
stations.push_back({ 0, 0, (int)1e9 });
stations.push_back({ D, 0, (int)1e9 });
sort(all(stations));
vector <int> max_fuel = { D };
for (auto item : stations)
max_fuel.push_back(item.B);
sort(all(max_fuel));
int hi = D;
for (auto d : max_fuel)
if (possible(d)) {
hi = d;
break;
}
int ans = -1;
int lo = 0;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (possible(mid))
ans = mid, hi = mid - 1;
else
lo = mid + 1;
}
cout << ans << '\n';
}
}
namespace sub47 {
const int mxN = 3e5 + 5;
struct dta {
int B, id;
bool operator < (const dta &other) const {
return B < other.B;
}
};
struct node {
int val, lazy;
} st[4 * mxN];
vector <dta> dta;
vector <int> compressed_X, compressed_B;
void down(int id) {
int t = st[id].lazy;
st[id << 1].val += t;
st[id << 1 | 1].val += t;
st[id << 1].lazy += t;
st[id << 1 | 1].lazy += t;
st[id].lazy = 0;
}
void build(int id, int left, int right) {
if (left == right)
return void(st[id].val = compressed_X[left - 1]);
int mid = (left + right) >> 1;
build(id << 1, left, mid);
build(id << 1 | 1, mid + 1, right);
st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
}
void update(int id, int left, int right, int l, int r, int val) {
if (r < left || right < l)
return;
if (l <= left && right <= r) {
st[id].lazy += val;
st[id].val += val;
return;
}
down(id);
int mid = (left + right) >> 1;
update(id << 1, left, mid, l, r, val);
update(id << 1 | 1, mid + 1, right, l, r, val);
st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
}
int get(int id, int left, int right, int pos) {
if (left == right)
return st[id].val;
down(id);
int mid = (left + right) >> 1;
if (pos <= mid)
return get(id << 1, left, mid, pos);
return get(id << 1 | 1, mid + 1, right, pos);
}
vector <pair <int, int>> query;
int find_ans(int f) {
int mn = 1e18, sum = f;
for (int i = 0; i < sz(stations); i++)
if (f <= stations[i].B)
query.push_back({ stations[i].X, stations[i].A });
sort(all(query));
int pre = 0;
for (auto it: query) {
sum = sum - (it.first - pre);
mn = min(mn, sum);
sum = sum + it.second;
pre = it.first;
}
return f - mn;
}
void solve() {
stations.push_back({ D, 0, (int)1e9 });
for (int i = 0; i < sz(stations); ++i) {
dta.push_back({ stations[i].B, i });
compressed_X.push_back(stations[i].X);
compressed_B.push_back(stations[i].B);
}
sort(all(dta));
sort(all(compressed_X));
sort(all(compressed_B));
compressed_X.erase(unique(all(compressed_X)), compressed_X.end());
compressed_B.erase(unique(all(compressed_B)), compressed_B.end());
int m = sz(compressed_X) - 1;
build(1, 1, m);
for (int i = 0; i < sz(stations); ++i) {
int pos = lower_bound(all(compressed_X), stations[i].X) - compressed_X.begin() + 1;
update(1, 1, m, pos + 1, m, -stations[i].A);
}
if (st[1].val <= compressed_B[0])
return void(cout << find_ans(compressed_B[0]) << '\n');
int id = 1;
for (int i = 1; i < sz(compressed_B); i++) {
int r = compressed_B[i - 1];
while (dta[id].B == r) {
int i = dta[id].id;
int pos = lower_bound(all(compressed_X), stations[i].X) - compressed_X.begin() + 1;
update(1, 1, m, pos + 1, m, stations[i].A);
id++;
}
if (st[1].val <= compressed_B[i])
return void(cout << find_ans(compressed_B[i]) << '\n');
}
}
}
void solve() {
cin >> N >> D;
stations = vector <FUELSTATION> (N);
for (auto &item : stations)
cin >> item.X >> item.A >> item.B;
// if (sub1 :: check_condition())
// sub1 :: solve();
// else if (sub2 :: check_condition)
// sub2 :: solve();
// else if (sub356 :: check_condition())
sub356 :: solve();
// else
// sub47 :: solve();
}
