Maximum Software Installation Value with Dependencies

You are given N software packages. Each software i occupies W_i disk space and has a value V_i. You have a computer with disk capacity M, and you want to install a subset of these packages so that the total value is maximized.

However, there is a dependency rule: software i can function only if its dependency D_i is installed (and by extension, all the dependencies of D_i). If D_i = 0, then software i has no dependency and will work once installed. A software can be installed at most once. Note that each software depends on at most one other software.

The task is to choose and install a valid set of software such that if a software is installed, all its (direct or indirect) dependencies are also installed, and the total occupied disk space does not exceed M. The objective is to maximize the total value (the sum of V_i for the software that are working properly).

The problem can be summarized by the following mathematical formulation:

Maximize \( \sum_{i \in S} V_i \)

subject to:

• \( \sum_{i \in S} W_i \le M \)
• If \( i \in S \) and \( D_i \neq 0 \), then \( D_i \in S \) (and recursively all dependencies of \( D_i \) must be in \( S \)).

Design an algorithm to compute the maximum achievable total value.

inputFormat

The input begins with a line containing two integers N and M — the number of software packages and the disk capacity respectively.

Then follow N lines, each containing three integers W_i, V_i, and D_i. Here, W_i represents the disk space occupied by software i, V_i represents its value, and D_i represents its dependency. If D_i is 0, then software i has no dependency.

outputFormat

Output a single integer, which is the maximum total value of the software that can be installed such that the disk capacity is not exceeded and all dependency constraints are satisfied.

sample

5 10
3 4 0
4 5 1
2 3 1
5 8 0
1 2 2

14