#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>max(l,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=L;i<MID;++i) add(X,val[i],a[i]);
        for(int i=MID;i<=R;++i) add(X,val[i],b[i]);
        if(check(X)){
            ret=MID;for(int i=L;i<=MID;++i) add(c,val[i],a[i]);
            L=MID+1;
        }
        else{
            for(int i=R;i>=MID;--i) add(c,val[i],b[i]);
            R=MID-1;
        }
    }
    p=R,sum+=1ll*ret;
    if(l==r) return ;
    if(ret && l<=mid-1){
        c=cur;for(int i=r;i>=mid;--i) add(c,val[i],a[i]);
        //for(int i=(l+mid-1)/2;i>max(ret,s);--i) add(c,val[i],b[i]);
        solve(l,mid-1,s,max(ret,s),c);
    }
    if(mid+1<=r){
        c=cur;for(int i=s;i<p;++i) add(c,val[i],a[i]);
        //for(int i=(mid+1+r)/2;i>t;--i) add(c,val[i],b[i]);
        solve(mid+1,r,max(ret,s),t,c);
    }
}
int x,y,z;ll u,v,w;vector<int> f;
int main(){
    //freopen("ex_backpack1.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;
}