#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10; int n,v;ll L; struct nd{ int a,b,c; }d[maxn]; struct bag{ vector<int>dp; void ins(int x,int y){ down(i,v,x)dp[i]=max(dp[i],dp[i-x]+y); }bool chk(){ ll res=0;up(i,0,v)res+=dp[i]; return res<=L; } }; int ans[maxn]; void ins(int l,int r,int op,bag&x){up(i,l,r)x.ins((!op)?d[i].a:d[i].b,d[i].c);} void work(int l,int r,int p,int q,bag&x){ if(p==q){up(i,l,r)ans[i]=p;return;} bag y=x;int mid=p+q>>1; ins(mid+1,q,0,x);ins(max(r+1,p),mid,1,x); function<int(int,int)>find=[&](int l,int r){ if(l==r){ ins(l,l,1,x); if(x.chk())return l;return l-1; } bag y=x;int mid=r-((r-l)>>1); ins(mid,r,1,x);ins(l,mid-1,0,x); if(!x.chk()){x=y;ins(mid,r,1,x);return find(l,mid-1);} else{x=y;ins(l,mid-1,0,x);return find(mid,r);} }; int pos=find(l,min(mid,r));x=y; if(l<=pos){ ins(mid+1,q,0,x);ins(pos+1,min(r,p-1),1,x); work(l,pos,p,mid,x);x=y; } if(pos<r){ ins(l,pos,0,x);ins(max(r+1,p),mid,1,x); work(pos+1,r,mid+1,q,x);x=y; } } void slv(){ n=read(),v=read(),L=read()*v; up(i,1,n)d[i].a=read(),d[i].b=read(),d[i].c=read(); bag a;a.dp.resize(v+1,0);work(1,n,1,n+1,a); ll res=0; up(i,1,n)res+=n+1-ans[i]; // printf("ans:");up(i,1,n)printf("%d ",ans[i]);puts(""); cout<<res; } int main(){ // freopen("buy.in","r",stdin),freopen("buy.out","w",stdout); slv(); return 0; }