#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* template start */ #define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++) #define all(i) i.begin(), i.end() #define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) void debug_out(){std::cerr< void debug_out(Head h,Tail... t){ std::cerr<<" "<0)std::cout<<" :"; debug_out(t...); } template std::ostream& operator<<(std::ostream& os, std::pair pa) { return os << pa.first << " " << pa.second; } template std::ostream& operator<<(std::ostream& os, std::vector vec) { for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os; } template inline bool chmax(T1& a,T2 b){return a inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);} long long pow_mod(long long a, long long b, long long mod=-1) { if(b==0)return 1; if ((a == 0)||(mod!=-1&&(a+mod)%mod==0))return 0; long long x = 1; while (b > 0) { if (b & 1)x = (mod!=-1)?(x * a) % mod:x*a; a = (mod!=-1)?(a * a) % mod:a*a; b >>= 1; } return x; } template class modint { using u64 = std::uint_fast64_t; public: u64 a; constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {} constexpr u64 &value() noexcept { return a; } constexpr const u64 &value() const noexcept { return a; } constexpr modint operator+(const modint rhs) const noexcept { return modint(*this) += rhs; } constexpr modint operator-(const modint rhs) const noexcept { return modint(*this) -= rhs; } constexpr modint operator*(const modint rhs) const noexcept { return modint(*this) *= rhs; } constexpr modint operator/(const modint rhs) const noexcept { return modint(*this) /= rhs; } constexpr modint &operator+=(const modint rhs) noexcept { a += rhs.a; if (a >= Modulus) { a -= Modulus; } return *this; } constexpr modint &operator-=(const modint rhs) noexcept { if (a < rhs.a) { a += Modulus; } a -= rhs.a; return *this; } constexpr modint &operator*=(const modint rhs) noexcept { a = a * rhs.a % Modulus; return *this; } constexpr modint &operator/=(modint rhs) noexcept { u64 exp = Modulus - 2; while (exp) { if (exp % 2) { *this *= rhs; } rhs *= rhs; exp /= 2; } return *this; } }; /* template end */ using ll = long long; using P=std::pair; constexpr ll INF=1e14; int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); ll N,V; std::cin>>N>>V; std::vector x(N+1),v(N),w(N); std::cin>>x[N]; rep(i,0,N){ std::cin>>x[i]>>v[i]>>w[i]; } std::vector> dp(N+1,std::vector(V+1,INF)); rep(i,0,V+1)dp[N][i]=0; for(ll i=N-1;i>=0;i--){ rep(j,0,V+1){ if(j-(x[i+1]-x[i])>=0)chmin(dp[i][j],dp[i+1][j-x[i+1]+x[i]]); ll tmp=std::min(V,j+v[i]); if(tmp-(x[i+1]-x[i])>=0)chmin(dp[i][j],dp[i+1][tmp-x[i+1]+x[i]]+w[i]); } } if(x[0]>V)std::cout<<-1<<"\n"; else{ if(dp[0][V-x[0]]==INF)std::cout<<-1<<"\n"; else std::cout<