#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;
}