Problem Description

The leaders of AC country made a decision to regain the TW Island. But they have to face the powerful force from USB. So the leaders have to hire some excellent soldiers from the training base called ALPC to format the most powerful force.
The followings are the consists of ALPC:
1.  There are more than one alpcs who are generals, like alpc04.
2.  Every alpc has a direct superior, except the generals.
3.  The alpc who has underling is an officer (Every officer’ number is no more than 500, like alpc21, alpc32).
4.  If send one alpc to the war, so will his direct superior. Of course the general’s direct superior is himself.
5.  Every alpc has two values. Vi is the fighting strength and Ci is the cost that the leader have to pay for the soldier.

Due to the AC country has limited financial resources, the leaders want to format the most powerful force with the cost not exceed G. Obviously, it is an uphill task! Therefore, the leaders of the AC country have assigned the task to alpc72 because of the outstanding behavior he had done at the ACM/ICPC. But alpc72 has been lost in hunting PLMM nowadays, so that he has no time to deal with this problem. What’s more, he left it to you.

Input

There will have several test cases.
The first line has two integers N and G, which stand for the total number of soldiers and the maximum cost. Soldiers numbered consequently from 1 to N. (1<=N<=100000, 1<=G<=10000)
The next N lines, each has three integers Ci, Vi and Fi. They are the cost, the measure of power and the direct superior of the ith soldier. (0<=Ci<=1000000, 0<=Vi<=1000000)

Output

Output one integer (must within 32 bits)as the maximum fighting strength of the most powerful force.

5 10
1 2 1
10 5 2
1 1 1 
1 1 1
1 1 3
5 10
1 2 1
2 4 2
1 1 1 
1 1 1
1 1 3

5
9

Hint

Special Thanks to alpc30.

Author

alpc32