#include <bits/stdc++.h> #include <atcoder/segtree> using namespace std; using namespace atcoder; using ll = long long; //using mint = modint998244353; ll op(ll a, ll b){ return max(a, b); } ll e(){ return 0; } int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* T_i-T_j >= abs(X_i-X_j) T_i-T_j >= X_i-X_j >= -T_i+T_j T_i-X_i >= T_j-X_j かつ T_i+X_i >= T_j+X_j Z_i = T_i-X_i W_i = T_i+X_iとすると、 Z_i >= Z_jかつW_i >= W_jのときにj->iへの遷移が可能。 2次元で重みつきLISを解く。 iをW, Zの昇順で並びかえ、セグメント木を使う。 初期点が(0,0)なのでZ,W<0となるものは無視する。 */ ll N, T, X, C, Z, W; cin >> N; vector<tuple<ll, ll, ll>> v; for (int i=0; i<N; i++){ cin >> T >> X >> C; Z = T-X; W = T+X; if (Z < 0 || W < 0) continue; v.push_back({Z, W, C}); } sort(v.begin(), v.end()); vector<ll> w; for (auto [Z, W, C] : v) w.push_back(W); sort(w.begin(), w.end()); w.erase(unique(w.begin(), w.end()), w.end()); segtree<ll, op, e> tree(N); for (auto [Z, W, C] : v){ int x = upper_bound(w.begin(), w.end(), W)-w.begin(); ll nxt = tree.prod(0, x)+C; x = lower_bound(w.begin(), w.end(), W)-w.begin(); tree.set(x, max(tree.get(x), nxt)); } cout << tree.all_prod() << endl; return 0; }