#include using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define per(i, n) for (int i = (n) - 1; i >= 0; i--) #define rep2(i, l, r) for (int i = (l); i < (r); i++) #define per2(i, l, r) for (int i = (r) - 1; i >= (l); i--) #define each(e, v) for (auto &e : v) #define MM << " " << #define pb push_back #define eb emplace_back #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)x.size() using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; template using minheap = priority_queue, greater>; template using maxheap = priority_queue; template bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; } template bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; } template int flg(T x, int i) { return (x >> i) & 1; } int pct(int x) { return __builtin_popcount(x); } int pct(ll x) { return __builtin_popcountll(x); } int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int botbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int botbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template void print(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' '); if (v.empty()) cout << '\n'; } template void printn(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << '\n'; } template void err_print(const vector &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cerr << v[i] + x << ' '; cerr << endl; } template int lb(const vector &v, T x) { return lower_bound(begin(v), end(v), x) - begin(v); } template int ub(const vector &v, T x) { return upper_bound(begin(v), end(v), x) - begin(v); } template void rearrange(vector &v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template vector id_sort(const vector &v, bool greater = false) { int n = v.size(); vector ret(n); iota(begin(ret), end(ret), 0); sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; }); return ret; } template void reorder(vector &a, const vector &ord) { int n = a.size(); vector b(n); for (int i = 0; i < n; i++) b[i] = a[ord[i]]; swap(a, b); } template T floor(T x, T y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x >= 0 ? x / y : (x - y + 1) / y); } template T ceil(T x, T y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x >= 0 ? (x + y - 1) / y : x / y); } template pair operator+(const pair &p, const pair &q) { return make_pair(p.first + q.first, p.second + q.second); } template pair operator-(const pair &p, const pair &q) { return make_pair(p.first - q.first, p.second - q.second); } template istream &operator>>(istream &is, pair &p) { S a; T b; is >> a >> b; p = make_pair(a, b); return is; } template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second; } struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); } } io_setup; constexpr int inf = (1 << 30) - 1; constexpr ll INF = (1LL << 60) - 1; // constexpr int MOD = 1000000007; constexpr int MOD = 998244353; template struct Segment_Tree { using M = typename Monoid::V; int n, m; vector seg; // f(f(a,b),c) = f(a,f(b,c)), f(e1,a) = f(a,e1) = a Segment_Tree(const vector &v) : n(v.size()) { m = 1; while (m < n) m <<= 1; seg.assign(2 * m, Monoid::id); copy(begin(v), end(v), begin(seg) + m); build(); } Segment_Tree(int n, M x = Monoid::id) : Segment_Tree(vector(n, x)) {} void set(int i, const M &x) { seg[m + i] = x; } void build() { for (int i = m - 1; i > 0; i--) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]); } void update(int i, const M &x, bool apply = false) { seg[i + m] = apply ? Monoid::merge(seg[i + m], x) : x; i += m; while (i >>= 1) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]); } M query(int l, int r) const { l = max(l, 0), r = min(r, n); M L = Monoid::id, R = Monoid::id; l += m, r += m; while (l < r) { if (l & 1) L = Monoid::merge(L, seg[l++]); if (r & 1) R = Monoid::merge(seg[--r], R); l >>= 1, r >>= 1; } return Monoid::merge(L, R); } M operator[](int i) const { return seg[m + i]; } template int find_subtree(int i, const C &check, M &x, int type) const { while (i < m) { M nxt = type ? Monoid::merge(seg[2 * i + type], x) : Monoid::merge(x, seg[2 * i + type]); if (check(nxt)) { i = 2 * i + type; } else { x = nxt; i = 2 * i + (type ^ 1); } } return i - m; } // check(区間 [l,r] での演算結果) を満たす最小の r (存在しなければ n) template int find_first(int l, const C &check) const { M L = Monoid::id; int a = l + m, b = 2 * m; while (a < b) { if (a & 1) { M nxt = Monoid::merge(L, seg[a]); if (check(nxt)) return find_subtree(a, check, L, 0); L = nxt; a++; } a >>= 1, b >>= 1; } return n; } // check((区間 [l,r) での演算結果)) を満たす最大の l (存在しなければ -1) template int find_last(int r, const C &check) const { M R = Monoid::id; int a = m, b = r + m; while (a < b) { if ((b & 1) || a == 1) { M nxt = Monoid::merge(seg[--b], R); if (check(nxt)) return find_subtree(b, check, R, 1); R = nxt; } a >>= 1, b >>= 1; } return -1; } }; // sum template struct Plus_Monoid { using V = T; static constexpr V merge(const V &a, const V &b) { return a + b; }; static const V id; }; template const T Plus_Monoid::id = 0; // prod template struct Product_Monoid { using V = T; static constexpr V merge(const V &a, const V &b) { return a * b; }; static const V id; }; template const T Product_Monoid::id = 1; // min template struct Min_Monoid { using V = T; static constexpr V merge(const V &a, const V &b) { return min(a, b); }; static const V id; }; template constexpr T Min_Monoid::id = numeric_limits::max() / 2; // max template struct Max_Monoid { using V = T; static constexpr V merge(V a, V b) { return max(a, b); }; static const V id; }; template constexpr T Max_Monoid::id = -(numeric_limits::max() / 2); // 代入 template struct Update_Monoid { using V = T; static constexpr V merge(const V &a, const V &b) { if (a == id) return b; if (b == id) return a; return b; } static const V id; }; template constexpr T Update_Monoid::id = numeric_limits::max(); // min count (T:最大値の型、S:個数の型) template struct Min_Count_Monoid { using V = pair; static constexpr V merge(const V &a, const V &b) { if (a.first < b.first) return a; if (a.first > b.first) return b; return V(a.first, a.second + b.second); } static const V id; }; template constexpr pair Min_Count_Monoid::id = make_pair(numeric_limits::max() / 2, 0); // max count (T:最大値の型、S:個数の型) template struct Max_Count_Monoid { using V = pair; static constexpr V merge(const V &a, const V &b) { if (a.first > b.first) return a; if (a.first < b.first) return b; return V(a.first, a.second + b.second); } static const V id; }; template constexpr pair Max_Count_Monoid::id = make_pair(-(numeric_limits::max() / 2), 0); // 一次関数 ax+b の合成 (左から順に作用) template struct Affine_Monoid { using V = pair; static constexpr V merge(const V &a, const V &b) { return V(a.first * b.first, a.second * b.first + b.second); }; static const V id; }; template const pair Affine_Monoid::id = make_pair(1, 0); // モノイドの直積 template struct Cartesian_Product_Monoid { using V1 = typename Monoid_1::V; using V2 = typename Monoid_2::V; using V = pair; static constexpr V merge(const V &a, const V &b) { return V(Monoid_1::merge(a.first, b.first), Monoid_2::merge(a.second, b.second)); } static const V id; }; template const pair Cartesian_Product_Monoid::id = make_pair(Monoid_1::id, Monoid_2::id); // 行列積 (l*r) template struct Matrix_Monoid { using V = array, n>; static constexpr V I() { V ret; for (int i = 0; i < n; i++) fill(begin(ret[i]), end(ret[i]), T(0)); for (int i = 0; i < n; i++) ret[i][i] = 1; return ret; } static constexpr V merge(V l, V r) { V ret; for (int i = 0; i < n; i++) fill(begin(ret[i]), end(ret[i]), T(0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) ret[i][k] += l[i][j] * r[j][k]; } } return ret; } static const V id; }; template const array, n> Matrix_Monoid::id = Matrix_Monoid::I(); // 行列積 (r*l) template struct Matrix_Monoid_Rev { using V = array, n>; static constexpr V I() { V ret; for (int i = 0; i < n; i++) fill(begin(ret[i]), end(ret[i]), T(0)); for (int i = 0; i < n; i++) ret[i][i] = 1; return ret; } static constexpr V merge(V l, V r) { V ret; for (int i = 0; i < n; i++) fill(begin(ret[i]), end(ret[i]), T(0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) ret[i][k] += r[i][j] * l[j][k]; } } return ret; } static const V id; }; template const array, n> Matrix_Monoid_Rev::id = Matrix_Monoid_Rev::I(); // range add range min template struct Min_Plus_Acted_Monoid { using Monoid = Min_Monoid; using Operator = Plus_Monoid; using M = T; using O = T; static constexpr M merge(const M &a, const O &b) { return a + b; }; }; // range add range max template struct Max_Plus_Acted_Monoid { using Monoid = Max_Monoid; using Operator = Plus_Monoid; using M = T; using O = T; static constexpr M merge(const M &a, const O &b) { return a + b; }; }; // range add range min count (T:最小値の型、S:個数の型) template struct Min_Count_Add_Acted_Monoid { using Monoid = Min_Count_Monoid; using Operator = Plus_Monoid; using M = pair; using O = T; static constexpr M merge(const M &a, const O &b) { return make_pair(a.first + b, a.second); }; }; // range add range max count (T:最大値の型、S:個数の型) template struct Max_Count_Add_Acted_Monoid { using Monoid = Max_Count_Monoid; using Operator = Plus_Monoid; using M = pair; using O = T; static constexpr M merge(const M &a, const O &b) { return make_pair(a.first + b, a.second); }; }; // range add range sum template struct Plus_Plus_Acted_Monoid { using Monoid = Cartesian_Product_Monoid, Plus_Monoid>; using Operator = Plus_Monoid; using M = pair; using O = T; static constexpr M merge(const M &a, const O &b) { return M(a.first + b * a.second, a.second); } }; // range update range sum template struct Plus_Update_Acted_Monoid { using Monoid = Cartesian_Product_Monoid, Plus_Monoid>; using Operator = Update_Monoid; using M = pair; using O = T; static constexpr M merge(const M &a, const O &b) { return b == Operator::id ? a : M(b * a.second, a.second); } }; // range update range min template struct Min_Update_Acted_Monoid { using Monoid = Min_Monoid; using Operator = Update_Monoid; using M = T; using O = T; static constexpr M merge(const M &a, const O &b) { return b == Operator::id ? a : b; } }; // range update range max template struct Max_Update_Acted_Monoid { using Monoid = Max_Monoid; using Operator = Update_Monoid; using M = T; using O = T; static constexpr M merge(const M &a, const O &b) { return b == Operator::id ? a : b; } }; // range affine range sum template struct Plus_Affine_Acted_Monoid { using Monoid = Cartesian_Product_Monoid, Plus_Monoid>; using Operator = Affine_Monoid; using M = pair; using O = pair; static constexpr M merge(const M &a, const O &b) { return M(b.first * a.first + b.second * a.second, a.second); }; }; void solve() { ll N, S, H; cin >> N >> S >> H; vector x(N), y(N), z(N); rep(i, N) cin >> x[i] >> y[i] >> z[i]; vector s(N + 1, 0); rep(i, N) s[i + 1] = s[i] + z[i]; Segment_Tree> seg(N, -INF); seg.update(0, 0); vector dp(N, -INF); ll ans = 0; rep(i, N) { if (dp[i] > 0) seg.update(i, dp[i] - s[i]); int j = lb(x, y[i] - S); if (j <= i) { ll tmp = seg.query(j, i + 1) + s[i + 1]; chmax(ans, tmp); int k = lb(x, y[i] + H); if (k < N) { chmax(dp[k], tmp); // } } if (i < N - 1) chmax(dp[i + 1], dp[i]); } cout << ans << '\n'; } int main() { int T = 1; // cin >> T; while (T--) solve(); }