#include<bits/stdc++.h> using namespace std; #define int 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=500010,N=26; bool AAA; int n,m,k,ans,sum,a[MAXN],b[MAXN],c[MAXN],as[MAXN]; vector<int>f[MAXN],R;int cnt; void ins(int x,int y){ cnt++; for(int i=1;i<=m;i++)f[cnt][i]=max({f[cnt][i-1],f[cnt-1][i],i>=x?f[cnt-1][i-x]+y:0}); } void pop(){cnt--;} int qry(){int res=0;for(int i=1;i<=m;i++)res+=f[cnt][i];return res;} // void prt(){for(int i=1;i<=m;i++)cout<<f[cnt][i]<<" ";cout<<endl;} void calc(int L,int R,int l,int r){ // cout<<" "<<L<<" "<<R<<" "<<l<<" "<<r<<":"<<endl; 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]);//,cout<<"ia"<<i<<endl; for(int i=max(R+1,l);i<=mid;i++)ins(b[i],c[i]);//,cout<<"ib"<<i<<endl; int tl=L,tr=min(mid,R); // cout<<" "<<tl<<" "<<tr<<endl; while(tl<tr){ int md=(tl+tr)>>1; for(int i=tl;i<md;i++)ins(a[i],c[i]);//,cout<<"ia"<<i<<endl; for(int i=tr;i>=md;i--)ins(b[i],c[i]);//,cout<<"ib"<<i<<endl; int tmp=qry(); for(int i=tl;i<=tr;i++)pop();//,cout<<"p"<<endl; // cout<<"CHK"<<(tmp>k)<<" "<<md<<endl; if(tmp>k){ for(int i=md+1;i<=tr;i++)ins(b[i],c[i]);//,cout<<"ib"<<i<<endl; tr=md; } else { for(int i=tl;i<=md;i++)ins(a[i],c[i]);//,cout<<"ia"<<i<<endl; tl=md+1; } } ins(a[tl],c[tl]);//,cout<<"ia"<<tl<<endl; if(qry()<=k)tl++;//,cout<<","; // for(int i=1;i<=m;i++)cout<<f[cnt][i]<<" ";cout<<endl; // cout<<" "<<tl<<" "<<endl; while(cnt>ttmp)pop();//,cout<<"p"<<endl; if(tl<=R){ for(int i=L;i<tl;i++)ins(a[i],c[i]);//,cout<<"IA"<<i<<endl; for(int i=R+1;i<=mid;i++)ins(b[i],c[i]);//,cout<<"IB"<<i<<endl; calc(tl,R,mid+1,r); while(cnt>ttmp)pop();//,cout<<"P"<<endl; } if(L<tl){ for(int i=tl;i<l;i++)ins(b[i],c[i]);//,cout<<"IB"<<i<<endl; for(int i=mid+1;i<=R;i++)ins(a[i],c[i]);//,cout<<"IA"<<i<<endl; calc(L,tl-1,l,mid); while(cnt>ttmp)pop();//,cout<<"P"<<endl; } } void slv(){ n=read(),m=read(),k=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; for(int i=0;i<=n+1;i++)for(int j=0;j<=m;j++)f[i].pb(0); calc(1,n,1,n+1); int 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; }