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

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

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

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

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

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

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

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

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

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

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

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

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

각 닌자 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 각 닌자의 리더십 레벨

닌자배치 (Dispatching) timer 1s memory 128MB

닌자배치 (Dispatching) 1s 128MB