#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v #define inx2(u) int I2=h[(u)],v2=edge[I2].v;I2;I2=edge[I2].nx,v=edge[I2].v int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=200010,N=10000010; bool AAA; int n,m,ans,sum,a[MAXN],b[MAXN],c[MAXN],as[MAXN],f[N];ll k; int cnt; // inline int max(int x,int y,int z){return x>z&&x>y?x:y>z?y:z;} int mp(int x,int y){return x*(m+1)+y;} void ins(int x,int y){ cnt++; for(int i=1;i<=m;++i)f[mp(cnt,i)]=i<x?f[mp(cnt-1,i)]:max(f[mp(cnt-1,i)],f[mp(cnt-1,i-x)]+y); } void pop(){cnt--;} ll qry(){ll res=0;int mx=0;for(int i=1;i<=m;i++)mx=max(mx,f[mp(cnt,i)]),res+=mx;return res;} void calc(int L,int R,int l,int r){ if(l==r){ for(int i=L;i<=R;i++)as[i]=l; return; } int mid=(l+r)>>1; int ttmp=cnt; for(int i=mid+1;i<=r;i++)ins(a[i],c[i]); for(int i=max(R+1,l);i<=mid;i++)ins(b[i],c[i]); int tl=L,tr=min(mid,R); while(tl<tr){ int md=(tl+tr+1)>>1; for(int i=tl;i<md;i++)ins(a[i],c[i]); for(int i=tr;i>=md;i--)ins(b[i],c[i]); ll tmp=qry(); if(tmp<=k){ for(int i=md;i<=tr;i++)pop(); tl=md; } else { for(int i=tl;i<=tr;i++)pop(); for(int i=md;i<=tr;i++)ins(b[i],c[i]); tr=md-1; } } ins(b[tl],c[tl]); if(qry()>k)tl--; while(cnt>ttmp)pop(); if(tl<R){ for(int i=L;i<=min(mid,tl);i++)ins(a[i],c[i]); for(int i=max(l,R+1);i<=mid;i++)ins(b[i],c[i]); calc(tl+1,R,mid+1,r); while(cnt>ttmp)pop(); } if(L<=tl){ for(int i=tl+1;i<=min(R,l-1);i++)ins(b[i],c[i]); for(int i=mid+1;i<=r;i++)ins(a[i],c[i]); calc(L,tl,l,mid); while(cnt>ttmp)pop(); } } void slv(){ n=read(),m=read(),k=(ll)read()*m; for(int i=1;i<=n;i++)a[i]=read(),b[i]=read(),c[i]=read(); // for(int i=1;i<=n;i++)c[i]=read(),a[i]=read(),b[i]=read(); c[n+1]=k,a[n+1]=m+1,b[n+1]=0; calc(1,n,1,n+1); ll ans=0; for(int i=1;i<=n;i++)ans+=n+1-as[i];//,cout<<as[i]<<" ";cout<<endl; printf("%lld\n",ans); } bool BBB; signed main(){ //freopen("1.in","r",stdin);freopen("1.out","w",stdout); // int _=read();while(_--) slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"<<((&AAA)-(&BBB))/1024.0/1024<<"MB\n"; return 0; }