#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i ) #define rep(i,n) REP(i,0,n) using ll = long long; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; template struct LazySegmentTree{ private: int n; vector node; vector lazy; T E0; S E1; inline void updatef(S& lazy,S& value){ lazy = min(lazy, value); } inline void calculatef(T& node,S& lazy,int len){ node = min(lazy, node) ; //区間maxとか } inline T queryf(T& x,T& y){ return min(x, y); } public: LazySegmentTree(int sz,T nodeE,S lazyE ):E0(nodeE), E1(lazyE){ n=1; while(n& v,T E0,S E1 ):E0(E0),E1(E1){ n=1; int sz=v.size(); while(n=0; --i){ node[i] = queryf(node[2*i+1],node[2*i+2]); } } void eval(int k,int l,int r){ if(lazy[k]==E1)return ; calculatef(node[k], lazy[k], r-l); if(r-l>1){ updatef(lazy[2*k+1], lazy[k]); updatef(lazy[2*k+2], lazy[k]); } lazy[k]=E1; } void update(int a, int b, S x,int k=0,int l=0,int r=-1){ if(r<0)r=n; eval(k,l,r); if(r<=a||b<=l)return; if(a<=l&&r<=b){ updatef(lazy[k], x); eval(k,l,r); } else { update(a,b,x,2*k+1,l,(l+r)/2); update(a,b,x,2*k+2,(l+r)/2,r); node[k]=queryf(node[2*k+1], node[2*k+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1){ if(r<0)r=n; eval(k,l,r); if(r<=a||b<=l)return E0; if(a<=l&&r<=b)return node[k]; T xl=query(a,b,2*k+1,l,(l+r)/2); T xr=query(a,b,2*k+2,(l+r)/2,r); return queryf(xl, xr); } }; int main(){ int n,v,l; cin>>n>>v>>l; vector x(n+1),a(n+1),w(n+1); rep(i,n){ cin>>x[i+1]>>a[i+1]>>w[i+1]; } a[0]=v; x.push_back(l); LazySegmentTree sg(n+2,longinf,longinf); sg.update(0,1,0); rep(i,n+1){ auto ret=sg.query(i,i+1); int idx=upper_bound(x.begin(),x.end(),x[i]+v)-x.begin(); sg.update(i+1,idx,ret+w[i]); } if(sg.query(n+1,n+2)==longinf)cout<<-1<