#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<vector> #include<sstream> #include<string> #include<climits> #include<set> #include<bitset> #include<cmath> #include<deque> #include<map> #include<queue> #define iinf 1000000000 #define linf 1000000000000000000LL #define dinf 1e200 #define all(v) (v).begin(),(v).end() #define sz(x) x.size() #define pb push_back #define mp make_pair #define lng long long #define sqr(a) ((a)*(a)) #define pii pair<int,int> #define pll pair<lng,lng> #define pss pair<string,string> #define pdd pair<double,double> #define X first #define Y second #define pi 3.14159265359 #define ff(i,xi,n) for(int i=xi;i<=(int)(n);++i) #define ffd(i,n) for(int i=xi;i>=(int)(n);--i) #define ffl(i,r) for(int i=head[r];i!=-1;i=edge[i].next) #define cc(i,j) memset(i,j,sizeof(i)) #define N 100001 #define M 200010 using namespace std; typedef vector<int> vi; typedef vector<string> vs; typedef unsigned int uint; typedef unsigned lng ulng; //Numberic Functions template<class T> inline T gcd(T a,T b)//NOTES:gcd( {if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);} template<class T> inline T lcm(T a,T b)//NOTES:lcm( {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));} template<class T> inline T euclide(T a,T b,T &x,T &y)//NOTES:euclide( {if(a<0){T d=euclide(-a,b,x,y);x=-x;return d;} if(b<0){T d=euclide(a,-b,y);y=-y;return d;} if(b==0){x=1;y=0;return a;}else{T d=euclide(b,a%b,y);T t=x;x=y;y=t-(a/b)*y;return d;}} template<class T> inline vector<pair<T,int> > factorize(T n)//NOTES:factorize( {vector<pair<T,int> > R;for (T i=2;n>1;){if (n%i==0){int C=0;for (;n%i==0;C++,n/=i);R.push_back(make_pair(i,C));} i++;if (i>n/i) i=n;}if (n>1) R.push_back(make_pair(n,1));return R;} template<class T> inline bool isPrimeNumber(T n)//NOTES:isPrimeNumber( {if(n<=1)return false;for (T i=2;i*i<=n;i++) if (n%i==0) return false;return true;} template<class T> inline T eularFunction(T n)//NOTES:eularFunction( {vector<pair<T,int> > R=factorize(n);T r=n;for (int i=0;i<R.size();i++)r=r/R[i].first*(R[i].first-1);return r;} template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;} template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;} template<class T> inline T Min(T x,T y){return (x>y?y:x);} template<class T> inline T Max(T x,T y){return (x<y?y:x);} struct pp{int v,next;}edge[2*N];int tot=0,n,m,val[N],cost[N],pos[N],dp[510][10001],p,head[N],ans; inline void addedge(int u,int v){edge[tot].v=v,edge[tot].next=head[u],head[u]=tot++;} void dfs(int r,int cap) { ffl(o,r) { int v=edge[o].v; ff(i,cap) dp[pos[v]][i]=dp[pos[r]][i]; dfs(v,cap-cost[v]); ff(i,cost[v],cap) checkmax(dp[pos[r]][i],dp[pos[v]][i-cost[v]]+val[v]); } } int main() { #ifdef DEBUG // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); #endif while(scanf("%d%d",&n,&m)==2) { cc(head,-1);cc(pos,0);cc(dp,0);tot=0,p=1,pos[0]=1,ans=0,cost[0]=0,val[0]=0; ff(i,1,n){int fa;scanf("%d%d%d",&cost[i],&val[i],&fa);if(fa==i) addedge(0,i);else { if(pos[fa]==0)pos[fa]=++p;addedge(fa,i);}} dfs(0,m);printf("%d\n",dp[1][m]); } return 0; } /* made by qinggege *
