#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10; int n,v,dp[maxn];ll L; struct nd{ int a,b,c; }d[maxn]; struct bag{ vector<int>dp; void ins(int x,int y){ down(i,v,x)dp[i]=max(dp[i],dp[i-x]+y); }bool chk(){ ll res=0;up(i,0,v)res+=dp[i]; return res<=L; } }; int ok[maxn]; struct tree{ vector<pi>v[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void bd(int l,int r,int p){ v[p].clear(); if(l==r)return; int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p)); } void modify(int l,int r,int s,int t,int p,pi x){ if(l<=s&&t<=r)return v[p].eb(x),void(); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),x);if(r>mid)modify(l,r,mid+1,t,rs(p),x); } void work(int l,int r,int p,bag&x){ bag y=x;for(auto [a,b]:v[p])x.ins(a,b); if(!x.chk()){ up(i,l,r)ok[i]=0;x=y; return; } if(l==r)ok[l]=x.chk(); else{ int mid=l+r>>1; work(l,mid,ls(p),x);work(mid+1,r,rs(p),x); }x=y; } }t; int l[maxn],r[maxn],p[maxn]; void slv(){ n=read(),v=read(),L=read()*v; up(i,1,n)d[i].a=read(),d[i].b=read(),d[i].c=read(); up(i,1,n)l[i]=i,r[i]=n+1; while(1){ bool ok=1; up(i,1,n)ok&=l[i]==r[i]; if(ok)break; up(i,1,n)p[i]=l[i]+r[i]>>1; t.bd(1,n,1); int pos=1; up(i,1,n){ if(i<n)t.modify(i+1,n,1,n,1,{d[i].a,d[i].c}); while(pos<=n&&p[pos]<i)pos++; if(pos>1)t.modify(1,pos-1,1,n,1,{d[i].a,d[i].c}); t.modify(pos,i,1,n,1,{d[i].b,d[i].c}); }bag a;a.dp.resize(v+1,0); t.work(1,n,1,a); up(i,1,n)if(l[i]!=r[i]){if(::ok[i])r[i]=p[i];else l[i]=p[i]+1;} up(i,2,n)l[i]=max(l[i],l[i-1]); down(i,n-1,1)r[i]=min(r[i],r[i+1]); } ll res=0; up(i,1,n)res+=n+1-l[i]; cout<<res; } int main(){ // freopen("buy.in","r",stdin),freopen("buy.out","w",stdout); slv(); return 0; }