abc390_e WA hand_09.txt
#include<bits/stdc++.h>
using namespace std;
long long n,x,dp[100010],dpp[100010],dppp[100010];
long long a[100010],v[100010],c[100010];
int main(){
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>v[i]>>a[i]>>c[i];
}
for(int i=1;i<=n;i++){
if(v[i]!=1)continue;
for(int j=x;j>=c[i];j--){
dp[j]=max(dp[j-c[i]]+a[i],dp[j]);
}
}
for(int i=1;i<=n;i++){
if(v[i]!=2)continue;
for(int j=x;j>=c[i];j--){
dpp[j]=max(dpp[j-c[i]]+a[i],dpp[j]);
}
}
for(int i=1;i<=n;i++){
if(v[i]!=3)continue;
for(int j=x;j>=c[i];j--){
dppp[j]=max(dppp[j-c[i]]+a[i],dppp[j]);
}
}
long long ans=-1;
for(int i=1;i<=x;i++){
for(int j=1;j<=x-i;j++){
int k=x-i-j;
ans=max(ans,min({dp[i],dpp[j],dppp[k]}));
}
}
cout<<ans<<"\n";
}