#pragma GCC optimize("O2,O3,Ofast,inline,unroll-loops")
#pragma GCC target("avx2,sse4")
#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
il void cmax(int &x,int y){x=x>y?x:y;}
il int read(){
int x=0,c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-48,c=getchar();
return x;
}
const int N=2e5+5;
int n,m,k,a[N],b[N],val[N];ll sum;
il void add(vector<int> &a,int v,int w){for(int i=k;i>=w;--i) cmax(a[i],a[i-w]+v);}
il int check(vector<int> a){
ll ret=0ll;
for(int i=0;i<=k;++i) ret+=1ll*a[i];
return ret<=1ll*m*k;
}
void solve(int l,int r,int s,int t,vector<int> cur){//cur:[1,l-1],[r+1,n]
if(l>r) return ;
int mid=(l+r)>>1,p=0,x,y,z,u,v,w,L,R,MID,ret=0;vector<int> c,X,d,c1,c2;
c=cur;
//for(int i=0;i<=k;++i) c[i]=0;
//for(int i=l;i<s;++i) add(c,val[i],a[i]);
for(int i=r;i>mid;--i) add(c,val[i],a[i]);
for(int i=mid;i>min(mid,t);--i) add(c,val[i],b[i]);
L=s,R=min(mid,t);
while(L<=R){
MID=(L+R)>>1,X=c;
for(int i=s;i<MID;++i) add(X,val[i],a[i]);
for(int i=MID;i<=min(mid,t);++i) add(X,val[i],b[i]);
/*if(MID==1){
printf("** %d : ",mid);
for(int i=1;i<=k;++i) printf("%d ",X[i]);puts("");
}*/
if(check(X)) ret=MID,L=MID+1;
else R=MID-1;
}
p=(ret?ret:s),sum+=1ll*ret;//printf("*** %d %d\n",mid,ret);
if(l==r) return ;
c=cur;for(int i=r;i>=mid;--i) add(c,val[i],a[i]);solve(l,mid-1,s,p,c);
c=cur;for(int i=s;i<p;++i) add(c,val[i],a[i]);solve(mid+1,r,p,t,c);
}
int x,y,z;ll u,v,w;vector<int> f;
int main(){
//freopen("ex_backpack3.in","r",stdin);
scanf("%d%d%d",&n,&k,&m);f.resize(k+1);for(int i=0;i<=k;++i) f[i]=0;
for(int i=1;i<=n;++i) val[i]=read(),a[i]=read(),b[i]=read();
for(int i=1;i<=n;++i) add(f,val[i],a[i]);
for(int i=1;i<=k;++i) w+=1ll*f[i];//printf("%d ",f[i]);puts("");
if(w<=1ll*m*k){printf("%lld",n*(n+1ll)/2ll);exit(0);}
for(int i=0;i<=k;++i) f[i]=0;
solve(1,n,1,n,f);
printf("%lld",sum);
return 0;
}