// >>> TEMPLATES #include using namespace std; using ll = long long; using ld = long double; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; #define int ll #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep1(i, n) for (int i = 1; i <= (int)(n); i++) #define repR(i, n) for (int i = (int)(n)-1; i >= 0; i--) #define rep1R(i, n) for (int i = (int)(n); i >= 1; i--) #define loop(i, a, B) for (int i = a; i B; i++) #define loopR(i, a, B) for (int i = a; i B; i--) #define all(x) begin(x), end(x) #define allR(x) rbegin(x), rend(x) #define pb push_back #define eb emplace_back #define fst first #define snd second template auto constexpr inf_ = numeric_limits::max()/2-1; auto constexpr INF32 = inf_; auto constexpr INF64 = inf_; auto constexpr INF = inf_; #ifdef LOCAL #include "debug.hpp" #else #define dump(...) (void)(0) #define say(x) (void)(0) #define debug if (0) #endif template struct pque : priority_queue, Comp> { vector &data() { return this->c; } void clear() { this->c.clear(); } }; template using pque_max = pque>; template using pque_min = pque>; template ::value, int> = 0> ostream& operator<<(ostream& os, T const& a) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; } template ::value, int> = 0> ostream& operator<<(ostream& os, const T (&a)[N]) { bool f = true; for (auto const& x : a) os << (f ? "" : " ") << x, f = false; return os; } template ())), class = typename enable_if::value>::type> istream& operator>>(istream& is, T &a) { for (auto& x : a) is >> x; return is; } template ostream& operator<<(ostream& os, pair const& p) { return os << p.first << " " << p.second; } template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup; template struct FixPoint : private F { constexpr FixPoint(F&& f) : F(forward(f)) {} template constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward(x)...); } }; struct MakeFixPoint { template constexpr auto operator|(F&& f) const { return FixPoint(forward(f)); } }; #define MFP MakeFixPoint()| #define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__) template struct vec_impl { using type = vector::type>; template static type make_v(size_t n, U&&... x) { return type(n, vec_impl::make_v(forward(x)...)); } }; template struct vec_impl { using type = T; static type make_v(T const& x = {}) { return x; } }; template using vec = typename vec_impl::type; template auto make_v(Args&&... args) { return vec_impl::make_v(forward(args)...); } template void quit(T const& x) { cout << x << endl; exit(0); } template constexpr bool chmin(T& x, U const& y) { if (x > (T)y) { x = (T)y; return true; } return false; } template constexpr bool chmax(T& x, U const& y) { if (x < (T)y) { x = (T)y; return true; } return false; } template constexpr auto sumof(It b, It e) { return accumulate(b, e, typename iterator_traits::value_type{}); } template int sz(T const& x) { return x.size(); } template int lbd(C const& v, T const& x) { return lower_bound(begin(v), end(v), x)-begin(v); } template int ubd(C const& v, T const& x) { return upper_bound(begin(v), end(v), x)-begin(v); } constexpr ll mod(ll x, ll m) { assert(m > 0); return (x %= m) < 0 ? x+m : x; } constexpr ll div_floor(ll x, ll y) { assert(y != 0); return x/y - ((x^y) < 0 and x%y); } constexpr ll div_ceil(ll x, ll y) { assert(y != 0); return x/y + ((x^y) > 0 and x%y); } constexpr int dx[] = { 1, 0, -1, 0, 1, -1, -1, 1 }; constexpr int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 }; constexpr int popcnt(ll x) { return __builtin_popcountll(x); } mt19937_64 seed_{random_device{}()}; template Int rand(Int a, Int b) { return uniform_int_distribution(a, b)(seed_); } i64 irand(i64 a, i64 b) { return rand(a, b); } // [a, b] u64 urand(u64 a, u64 b) { return rand(a, b); } // template void shuffle(It l, It r) { shuffle(l, r, seed_); } template V &operator--(V &v) { for (auto &x : v) --x; return v; } template V &operator++(V &v) { for (auto &x : v) ++x; return v; } bool next_product(vector &v, int m) { repR (i, v.size()) if (++v[i] < m) return true; else v[i] = 0; return false; } bool next_product(vector &v, vector const& s) { repR (i, v.size()) if (++v[i] < s[i]) return true; else v[i] = 0; return false; } template int sort_unique(vec &v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); return v.size(); } template auto prefix_sum(V const& a) { vector s; s.reserve(a.size() + 1); s.push_back(0); for (auto const& x : a) s.emplace_back(s.back() + x); return s; } template auto suffix_sum(V const& a) { vector s(a.size() + 1); int pos = a.size(); for (auto it = a.rbegin(); it != a.rend(); ++it, --pos) { s[pos-1] = *it + s[pos]; } return s; } // <<< // >>> segment tree 2d (compressed) template struct Segtree2D : Handler { using Value = typename Handler::Value; using Handler::unit_value; // () -> Value using Handler::merge; // (Value, Value) -> Value // >>> internal segtree struct segtree { // compressed vector v; vector ys; size_t n; segtree() = default; void add(Int y, Value const& val) { size_t i = lower_bound(ys.begin(), ys.end(), y) - ys.begin(); assert(i < n && ys[i] == y); for (i += n; i; i >>= 1) v[i] = merge(v[i], val); } void set(Int y, Value const& val) { size_t i = lower_bound(ys.begin(), ys.end(), y) - ys.begin(); assert(i < n && ys[i] == y); v[i + n] = val; i += n; while (i > 1) i >>= 1, v[i] = merge(v[i << 1], v[i << 1 | 1]); } Value get(Int y) const { return get(y, y+1); } Value get(Int yl, Int yr) const { size_t l = lower_bound(ys.begin(), ys.end(), yl) - ys.begin(); size_t r = lower_bound(ys.begin(), ys.end(), yr) - ys.begin(); assert(l <= r); Value L = unit_value(), R = unit_value(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) L = merge(L, v[l++]); if (r & 1) R = merge(v[--r], R); } return merge(L, R); } }; // <<< vector> pos; bool built = false; vector seg; size_t n; Segtree2D() = default; void add_point(Int x, Int y) { pos.emplace_back(x, y); built = false; } void build() { sort(pos.begin(), pos.end()); pos.erase(unique(pos.begin(), pos.end()), pos.end()); n = pos.size(); seg.resize(n << 1); for (size_t i = 0; i < n; ++i) { seg[i + n].ys.push_back(pos[i].second); seg[i + n].n = 1; seg[i + n].v.resize(2, unit_value()); } for (size_t i = n - 1; i; --i) { auto const& L = seg[i << 1].ys, R = seg[i << 1 | 1].ys; auto &P = seg[i].ys; P.resize(L.size() + R.size()); std::merge(L.begin(), L.end(), R.begin(), R.end(), P.begin()); P.erase(unique(P.begin(), P.end()), P.end()); seg[i].n = P.size(); seg[i].v.resize(P.size() << 1, unit_value()); } built = true; } size_t x_index(Int x) const { auto const minf = numeric_limits::min(); return lower_bound(pos.begin(), pos.end(), make_pair(x, minf)) - pos.begin(); } void set(Int x, Int y, Value val) { assert(built); size_t i = lower_bound(pos.begin(), pos.end(), make_pair(x, y)) - pos.begin(); assert(i < n && pos[i] == make_pair(x, y)); seg[i += n].set(y, val); while (i > 1) { val = merge(val, seg[i ^ 1].get(y)); seg[i >>= 1].set(y, val); } } void add(Int x, Int y, Value const& val) { assert(built); size_t i = lower_bound(pos.begin(), pos.end(), make_pair(x, y)) - pos.begin(); assert(i < n && pos[i] == make_pair(x, y)); for (i += n; i; i >>= 1) seg[i].add(y, val); } Value get(Int x, Int y) const { return get(x, x + 1, y, y + 1); } Value get(Int xl, Int xr, Int yl, Int yr) const { assert(built); size_t l = x_index(xl), r = x_index(xr); assert(l <= r); Value L = unit_value(), R = unit_value(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) L = merge(L, seg[l++].get(yl, yr)); if (r & 1) R = merge(seg[--r].get(yl, yr), R); } return merge(L, R); } int size() const { return pos.size(); } vector dat() const { assert(built); vector ret; for (auto [x, y] : pos) ret.push_back(get(x, y)); return ret; } }; // <<< struct Max { using Value = int; constexpr static Value unit_value() { return -INF; } constexpr static Value merge(Value const& x, Value const& y) { return max(x, y); } }; int32_t main() { int n; cin >> n; vector> txv; Segtree2D seg; seg.add_point(0, 0); rep (i, n) { int t, x, v; cin >> t >> x >> v; txv.eb(t, x, v); seg.add_point(t+x, t-x); } sort(all(txv)); seg.build(); seg.set(0, 0, 0); int ma = 0; for (auto [t, x, v] : txv) { int val = seg.get(-INF, t+x+1, -INF, t-x+1) + v; seg.set(t+x, t-x, val); chmax(ma, val); } cout << ma << '\n'; }