닌자배치

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

이 닌자 조직에서는 마스터라고 불리는 닌자 한 명이 있고, 마스터 닌자를 제외한 모든 닌자는 오직 한 명의 보스를 모시고 있다. 닌자들의 비밀을 유지하고, 리더십을 보장하기 위해 오직 보스만이 자신의 부하들에게 명령을 지시한다. 보스 이외의 다른 사람이 명령을 전달하는 것은 철저히 금지되어 있다. 당신은 조직 내 한 그룹의 닌자를 모아 고객 한 명에게 배치하려고 한다. 당신은 배치된 닌자들에게 월급을 준다. 각 닌자들은 자신이 받는 월급이 고정되어 있다. 닌자들에게 주는 월급의 총 액수는 주어진 예산 범위 안이어야만 한다. 더욱이, 명령을 전달하기 위해서는 당신은 한 명의 닌자를 매니저로 정하고, 그 매니저가 배치된 모든 닌자에게 명령을 전달하도록 한다. 명령이 지시가 되면, 배치가 안 된 닌자라도 그 명령이 전달될 수 있다.. 매니저는 배치에 동원될 수도 있고, 동원이 안될 수도 있다. 만약, 배치가 안되면, 월급은 없다.

당신은 주어진 예산안에서 고객의 만족도를 극대화하려고 한다. 고객의 만족도는 배치된 닌자의 총 수와 매니저의 리더십 레벨의 곱으로 계산이 된다. 각각의 닌자의 리더십 레벨은 고정이 되어 있다.

각 닌자 i (1 ≤ i ≤ N) 에 대해 보스 Bi, 월급 Ci, 그리고 리더십 레벨 Li가 주어지고, 그리고 월급으로 줄 수 있는 예산 M이 주어졌을 때, 매니저와 배치된 닌자가 주어진 조건을 만족하도록 선택이 되었을 때, 고객 만족도의 최댓값을 출력하는 프로그램을 작성하시오.

입력의 첫 번째 줄에 두 개의 자연수 N, M이 공백을 두고 주어진다. 여기서 N 닌자의 수이고, M은 총 예산이다.

그 다음의 N줄에 각 닌자의 보스, 월급, 그리고 리더십 레벨이 나온다. (i+1)-번째 줄에 세 개의 자연수 Bi, Ci, Li가 하나의 공백을 사이에 두고 주어진다. 여기서 Bi는 닌자 i의 보스이고, Ci는 닌자 i의 월급을, 그리고 Li는 닌자 i의 리더십 레벨을 표시한다. 만일 Bi = 0이면, 닌자 i는 마스터이다. Bi < i가 항상 만족되어야 하므로, 각 닌자에 대해 자신의 보스 번호는 항상 그 닌자의 번호보다 작다.

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

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 1,000,000,000
• 0 ≤ Bi ≤ i
• 1 ≤ Ci ≤ M
• 1 ≤ Li ≤ 1,000,000,000

만일 닌자 1을 매니저로 선택하고, 닌자 3과 4를 배치하면, 월급의 총 액수는 4이고 이 액수는 예산 4를 초과하지 않는다. 배치된 닌자의 수가 2명이므로, 매니저의 리더십 레벨은 3이고, 고객의 만족도는 6이 된다. 이 값은 최대 값이다.