#pragma GCC optimize("Ofast") #include // #include // #include // #include // using namespace __gnu_pbds; // #include // namespace multiprecisioninteger = boost::multiprecision; // using cint=multiprecisioninteger::cpp_int; using namespace std; using ll=long long; #define double long double using datas=pair; using ddatas=pair; using tdata=pair; using vec=vector; using mat=vector; using pvec=vector; using pmat=vector; // using llset=tree,rb_tree_tag,tree_order_statistics_node_update>; #define For(i,a,b) for(i=a;i<(ll)b;++i) #define bFor(i,b,a) for(i=b,--i;i>=(ll)a;--i) #define rep(i,N) For(i,0,N) #define rep1(i,N) For(i,1,N) #define brep(i,N) bFor(i,N,0) #define brep1(i,N) bFor(i,N,1) #define all(v) (v).begin(),(v).end() #define allr(v) (v).rbegin(),(v).rend() #define vsort(v) sort(all(v)) #define vrsort(v) sort(allr(v)) #define endl "\n" #define eb emplace_back #define print(v) cout< inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} using P=pair; int main(){ // int codeforces;cin>>codeforces;while(codeforces--){ ll ans=-1; int i,j=0,k,f=0,N,V,L; scanf("%d %d %d",&N,&V,&L); scanf("%d %d %d",&i,&j,&k); if(i!=0){++N;f=1;} vector ax(N,0),v(N,0),w(N,0); ax[f]=i;v[f]=min(j,V);w[f]=k; rep1(i,N-f){ cin>>ax[i+f]>>v[i+f]>>w[i+f]; chmin(v[i+f],V); } if(ax[N-1]!=L){ ++N; ax.eb(L);v.eb(0);w.eb(0); } vector dist(N*(V+1)*2,inf); priority_queue,greater

> que; que.push(P(0,V*2+1)); while(!que.empty()){ P x=que.top();que.pop(); if(!chmin(dist[x.second],x.first))continue; i=x.second/((V+1)<<1); j=x.second%((V+1)<<1); if(i==N-1){ ans=x.first; break; } if(j<=V){ que.push(P(x.first+w[i],min(j+v[i],V)+i*((V+1)<<1)+V+1)); }else{ j-=V+1; } if(j>=ax[i+1]-ax[i]){ que.push(P(x.first,(i+1)*((V+1)<<1)+j+ax[i]-ax[i+1])); } } printf("%lld\n",ans); }