#include <bits/stdc++.h>
using namespace std;
struct triplet {
int x, y, z;
triplet() : x(0), y(0), z(0) {}
auto operator<=>(const triplet &r) const = default;
};
const int inf = 5e8;
class lazy_segment_tree {
int n;
vector<int> seg, lazy;
void push(int v) {
seg[v] += lazy[v];
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
lazy[v] = 0;
}
void pull(int v) { seg[v] = max(seg[2 * v], seg[2 * v + 1]); }
void add(int v, int tl, int tr, int l, int r, int del) {
push(v);
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] += del;
push(v);
return;
}
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, del);
add(2 * v + 1, tm + 1, tr, l, r, del);
pull(v);
}
int query(int v, int tl, int tr, int l, int r) {
push(v);
if (tr < l || r < tl) {
return -inf;
}
if (l <= tl && tr <= r) {
return seg[v];
}
int tm = (tl + tr) / 2;
return max(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
}
template <typename Fn>
int min_right(int v, int tl, int tr, int l, const Fn &f) {
push(v);
if (!f(seg[v]) || tr < l) {
return n;
}
if (tl == tr) {
return tl;
}
int tm = (tl + tr) / 2;
int ans = min_right(2 * v, tl, tm, l, f);
if (ans != n) {
return ans;
}
return min_right(2 * v + 1, tm + 1, tr, l, f);
}
public:
lazy_segment_tree(int n) : n(n), seg(4 * n), lazy(8 * n) {}
void add(int l, int r, int del) { add(1, 0, n - 1, l, r, del); }
int query(int l, int r) { return query(1, 0, n - 1, l, r); }
template <typename Fn>
int min_right(int l, const Fn &f) { return min_right(1, 0, n - 1, l, f); }
};
struct point {
int y, z;
};
class data_structure {
vector<int> buff;
vector<int> at_y;
lazy_segment_tree pref_max;
lazy_segment_tree opt;
lazy_segment_tree activate;
int compr(int x) { return lower_bound(buff.begin(), buff.end(), x) - buff.begin(); }
bool is_active(int y) {
return pref_max.query(y, y) - at_y[y] > 0;
}
void incr_range(int l, int r, int del) {
pref_max.add(l, r, del);
activate.add(l, r, del);
opt.add(l, r, del);
}
void chmax(int i, int x) { // st[i] = max(st[i], x)
int old = pref_max.query(i, i);
if (x <= old) {
return;
}
// we may need to update pref_max[i/i+1/i+2/...]
for (int l = i, r; l < buff.size() + 1; l = r) {
int val = pref_max.query(l, l);
r = pref_max.min_right(l, [&](int x) { return x > val; });
if (x - val <= 0) {
break;
}
incr_range(l, r - 1, x - val);
}
}
void activate_vals() {
auto fn = [&](int x) { return x > 0; };
for (int i = activate.min_right(0, fn); i != buff.size() + 1; i = activate.min_right(0, fn)) {
opt.add(i, i, inf); // undo -inf deactivated buff, activate
activate.add(i, i, -inf); // an already active value won't be activated again
}
}
public:
data_structure(const vector<int> &buff) : buff(buff), at_y(buff.size(), inf), pref_max(buff.size() + 1), opt(buff.size() + 1), activate(buff.size() + 1) {
pref_max.add(0, buff.size(), -inf);
for (int i = 0; i <= buff.size(); ++i) {
opt.add(i, i, (i < buff.size() ? buff[i] : 0) + (-inf) - inf); // buff[i] + st.query(0, i), and -inf because deactivated
activate.add(i, i, (-inf) - at_y[i]);
}
}
void add(int y, int z) {
y = compr(y);
activate.add(y, y, at_y[y]);
at_y[y] = min(at_y[y], z);
activate.add(y, y, -at_y[y]);
chmax(y + 1, z);
activate_vals();
}
int query(int Y, int Z) {
int ans = -inf;
int y = max(pref_max.min_right(0, [&](int x) { return x > Z; }), compr(Y + 1));
if (y > buff.size() - 1) {
return ans;
}
return max(ans, opt.query(y, buff.size() - 1));
}
};
int solve(int n, vector<triplet> a) {
vector<int> buff;
for (auto &[x, y, z] : a) {
buff.push_back(y), buff.push_back(y - 1), buff.push_back(y + 1);
}
sort(buff.begin(), buff.end());
buff.erase(unique(buff.begin(), buff.end()), buff.end());
data_structure ds(buff);
int ans = -1;
for (int i = 0, j = 0; i < n; ++i) {
while (j < i && a[j].x < a[i].x) {
ds.add(a[j].y, a[j].z);
j++;
}
ans = max(ans, a[i].x + ds.query(a[i].y, a[i].z));
}
return ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<triplet> a(n);
for (auto &[x, y, z] : a) {
cin >> x >> y >> z;
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
n = a.size();
int ans = solve(n, a);
for (auto &[x, y, z] : a) {
swap(y, z);
}
cout << max(ans, solve(n, a)) << '\n';
}
