문제
한 닌자 조직에서는 한 고객에게 닌자들을 배치하고, 닌자들이 그 고객을 위해 한 일에 대해 보상을 해주고 있다.
이 닌자 조직에서는 마스터라고 불리는 닌자 한 명이 있고, 마스터 닌자를 제외한 모든 닌자는 오직 한 명의 보스를 모시고 있다.
닌자들의 비밀을 유지하고, 리더십을 보장하기 위해 오직 보스만이 자신의 부하들에게 명령을 지시한다.
보스 이외의 다른 사람이 명령을 전달하는 것은 철저히 금지되어 있다.
당신은 조직 내 한 그룹의 닌자를 모아 고객 한 명에게 배치하려고 한다.
당신은 배치된 닌자들에게 월급을 준다.
각 닌자들은 자신이 받는 월급이 고정되어 있다.
난자들에게 주는 월급의 총 액수는 주어진 예산 범위 안이어야만 한다.
더욱이, 명령을 전달하기 위해서는 당신은 한 명의 닌자를 매니저로 정하고, 그 매니저가 배치된 모든 닌자에게 명령을 전달하도록 한다.
명령이 지시가 되면, 배치가 안된 닌자라도 그 명령을 전달할 수 있다.
매니저는 배치에 동원될 수도 있고, 동원이 안될 수도 있다. 만약, 배치가 안되면, 월급은 없다.
당신은 주어진 예산안에서 고객의 만족도를 극대화하려고 한다.
고객의 만족도는 배치된 닌자의 총 수와 매니저의 리더십 레벨의 곱으로 계산이 된다. 각각의 닌자의 리더십 레벨은 고정이 되어 있다.
각 닌자 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 이다.
예제
5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1
6
로그인해야 코드를 작성할 수 있어요.