Sakura Viewing Optimization

In the garden of Ai Yuanchou, there are n sakura trees, each having an aesthetic value C_i (0 ≤ C_i ≤ 200). Every morning before school, Ai Yuanchou comes to enjoy the blossoms. Being a biology genius, he appreciates each sakura tree in a peculiar way:

• For one type of tree, he can only view it once.
• For another type of tree, he can view it at most P_i times (1 ≤ P_i ≤ 100).
• For the third type of tree, he can view it an unlimited number of times.

However, each viewing of the i-th tree takes T_i time (0 ≤ T_i ≤ 100). With a limited amount of time available before school, determine the optimal combination of viewings (you may view a tree multiple times, but not exceeding its allowed number) so that the total aesthetic value is maximized while ensuring that Ai Yuanchou leaves on time (or early).

Note on Input Format: The input begins with two integers n and M where M is the total time available. Then there are n lines, each representing a tree with three integers:

• C: the aesthetic value of the tree.
• T: the time required for one viewing.
• P: a parameter indicating the view limit. If P is a positive integer, then it represents the maximum number of times this tree can be viewed (note that if the tree is of the one-view type, P will be 1). If P is -1, then the tree can be viewed an unlimited number of times.

Constraints:

• 1 ≤ n ≤ (upper limit unspecified)
• 0 ≤ C_i ≤ 200
• 0 ≤ T_i ≤ 100
• P = -1 or 1 ≤ P ≤ 100
• M is a non-negative integer representing available time.

Mathematical Formulation:

Let dp[j] be the maximum total aesthetic value achievable using exactly j units of time (0 ≤ j ≤ M). For each tree, treat it as an item with cost T_i and value C_i. If the tree is of the bounded type (P ≠ -1), you can take at most P_i copies. If it is unbounded (P = -1), you can take it any number of times. The goal is to compute dp[M].

Use techniques from the knapsack problem: for bounded items use binary splitting (also known as binary optimization) and for unbounded items use the complete knapsack approach. All formulas are given in \(\LaTeX\) where needed.

The recurrence for a knapsack item is:

\[ dp[j] = \max\left( dp[j],\ dp[j - cost] + value \right) \quad \text{for } j \geq cost. \]

inputFormat

The first line contains two integers n and M separated by a space, where n is the number of sakura trees and M is the total available time. The following n lines each contain three integers C, T, and P:

• C (0 ≤ C ≤ 200): Aesthetic value for the tree.
• T (0 ≤ T ≤ 100): The time needed for one viewing of the tree.
• P: The viewing limit for the tree. If P = -1, the tree can be viewed unlimited times. Otherwise, 1 ≤ P ≤ 100, where P = 1 indicates that the tree can be viewed only once, while larger positive values indicate the maximum number of viewings allowed.

All integers in a line are seperated by single spaces.

outputFormat

Output a single integer: the maximum total aesthetic value achievable without exceeding the available time M.

sample

3 10
10 2 1
5 1 3
6 3 -1

31