한 닌자 조직에서는 한 고객에게 닌자들을 배치하고, 닌자들이 그 고객을 위해 한 일에 대해 보상을 해주고 있다.

이 닌자 조직에서는 마스터라고 불리는 닌자 한 명이 있고, 마스터 닌자를 제외한 모든 닌자는 오직 한 명의 보스를 모시고 있다. 

닌자들의 비밀을 유지하고, 리더십을 보장하기 위해 오직 보스만이 자신의 부하들에게 명령을 지시한다. 

보스 이외의 다른 사람이 명령을 전달하는 것은 철저히 금지되어 있다. 

당신은 조직 내 한 그룹의 닌자를 모아 고객 한 명에게 배치하려고 한다. 

당신은 배치된 닌자들에게 월급을 준다. 

각 닌자들은 자신이 받는 월급이 고정되어 있다. 

난자들에게 주는 월급의 총 액수는 주어진 예산 범위 안이어야만 한다. 

더욱이, 명령을 전달하기 위해서는 당신은 한 명의 닌자를 매니저로 정하고, 그 매니저가 배치된 모든 닌자에게 명령을 전달하도록 한다. 

명령이 지시가 되면, 배치가 안된 닌자라도 그 명령을 전달할 수 있다. 

매니저는 배치에 동원될 수도 있고, 동원이 안될 수도 있다. 만약, 배치가 안되면, 월급은 없다.

당신은 주어진 예산안에서 고객의 만족도를 극대화하려고 한다. 

고객의 만족도는 배치된 닌자의 총 수와 매니저의 리더십 레벨의 곱으로 계산이 된다. 각각의 닌자의 리더십 레벨은 고정이 되어 있다.

각 닌자 i(1≤i≤N)에 대해 보스 Bi, 월급 Ci, 그리고 리더십 레벨 Li가 주어지고, 

그리고 월급으로 줄 수 있는 예산 M이 주어졌을 때, 

매니저와 배치된 닌자가 주어진 조건을 만족하도록 선택이 되었을 때, 

고객 만족도의 최대값을 출력하는 프로그램을 작성하시오.

[제약조건]

1≤N≤100,000 닌자의 수

1≤M≤1,000,000,000 월급을 주기 위한 총 예산

0≤Bi≤i 닌자의 보스

1≤Ci≤M 각 닌자의 월급

1≤Li≤1,000,000,000 각 닌자의 리더십 레벨

입력의 첫 번째줄에 두 개의 자연수 N, M이 공백을 두고 주어진다.

여기서 N은 닌자의 수이고, M은 총 예산이다. 

그 다음의 N줄에 각닌자의 보스, 월급, 그리고 리더십 레벨이 나온다. (i+1) - 번째 줄에 세개의 자연수 Bi, Ci, Li가 하나의 공백을 사이에 두고 주어진다. 

여기서 Bi는 닌자 i의 보스이고, Ci는 닌자 i의 월급을, 그리고 Li는 닌자 i의 리더십 레벨을 표시한다. 

만일 Bi=0이면, 닌자 i는 마스터이다. Bi < i 가 항상 만족이 되어야 하므로, 각 닌자에 대해 자신의 보스 번호는 항상 그 닌자의 번호보다 작다.

첫줄에 고객의 만족도가 최대가 되는 값을 출력한다.

[참고] 전체 점수의30%에해당하는 테스트데이터는 N≤3,000 이다.

만일 닌자 1을 매니저로 선택하고, 닌자 3과 4를 배치하면, 월급의 총 액수는 4이고 이 액수는 예산 4를 초과하지 않는다.

배치된 닌자의 수가 2명이므로, 매니저의 리더십 레벨은 3이고, 고객의 만족도는 6이된다. 이 값은 최대 값이다.