#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=200010; bool AAA; int n,m,k,ans,sum,a[MAXN],b[MAXN],c[MAXN],as[MAXN]; vector<int>f[MAXN],R;int cnt;int tp[MAXN],stk[MAXN]; 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<<" "<<cnt<<":"<<endl; // for(int i=1;i<=n/4;i++)cout<<tp[i];cout<<' '; // for(int i=1;i<=n/4;i++)cout<<tp[i+n/4];cout<<' '; // for(int i=1;i<=n/4;i++)cout<<tp[i+n/2];cout<<' '; // for(int i=1;i<=n/4+1;i++)cout<<tp[i+n/4*3];cout<<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)>>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(); // prt(); for(int i=tl;i<=tr;i++)pop();//,cout<<"p"<<endl; // cout<<"CHK "<<tmp<<" "<<k<<" "<<md<<endl; if(tmp<=k){ for(int i=tl;i<md;i++)ins(a[i],c[i]);//,cout<<"ia"<<i<<endl; tl=md; } else { for(int i=md;i<=tr;i++)ins(b[i],c[i]);//,cout<<"ib"<<i<<endl; tr=md-1; } } ins(b[tl],c[tl]);//,cout<<"ib"<<tl<<endl; if(qry()>k)tl--;//,cout<<","; // for(int i=1;i<=m;i++)cout<<f[cnt][i]<<" ";cout<<endl; // cout<<" "<<tl<<" "<<endl; // cout<<cnt<<" "<<ttmp<<endl; // for(int i=1;i<=cnt;i++)cout<<tp[i]<<" ";cout<<endl; while(cnt>ttmp)pop();//,cout<<"p"<<endl; if(tl<R){ for(int i=L;i<=min(mid,tl);i++)ins(a[i],c[i]),assert(!tp[i]),tp[i]=1,stk[cnt]=i;//,cout<<"IA"<<i<<endl; for(int i=max(l,R+1);i<=mid;i++)ins(b[i],c[i]),assert(!tp[i]),tp[i]=2,stk[cnt]=i;//,cout<<"IB"<<i<<endl; calc(tl+1,R,mid+1,r); while(cnt>ttmp)assert(tp[stk[cnt]]),tp[stk[cnt]]=0,pop();//,cout<<"P"<<endl; } if(L<=tl){ // cerr<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<mid<<endl; for(int i=tl+1;i<min(R,l);i++)ins(b[i],c[i]),assert(!tp[i]),tp[i]=2,stk[cnt]=i;//,cout<<"IB"<<i<<endl; for(int i=mid+1;i<=r;i++)ins(a[i],c[i]),assert(!tp[i]),tp[i]=1,stk[cnt]=i;//,cout<<"IA"<<i<<endl; calc(L,tl,l,mid); while(cnt>ttmp)assert(tp[stk[cnt]]),tp[stk[cnt]]=0,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; }