0/1 Knapsack Problem

You are given a knapsack with a weight capacity (W) and (N) items. Each item is described by three integers: an identifier, its weight, and its value. Your task is to determine the maximum total value of items that can be placed in the knapsack without exceeding the weight capacity.

Formally, given items ({(id_i, w_i, v_i)}{i=1}^{N}), find a subset (S) such that (\sum{i \in S} w_i \leq W) and the total value (\sum_{i \in S} v_i) is maximized. A dynamic programming solution typically uses the recurrence: [ dp[w] = \max{ dp[w],\ dp[w - w_i] + v_i }\quad\text{for } w \geq w_i ]

Note: Each item can be chosen at most once.

inputFormat

The first line contains two integers (N) and (W) separated by a space, where (N) is the number of items and (W) is the maximum weight capacity of the knapsack. Each of the following (N) lines contains three integers: the item identifier, the weight of the item, and the value of the item.

outputFormat

Output a single integer on a line by itself: the maximum total value that can be achieved by packing items into the knapsack without exceeding the weight limit.## sample

4 50
1 10 60
2 20 100
3 30 120
4 40 150

220